Minimum Number of Platforms in DSA Java - Build from Scratch

Minimum Number of Platforms

📖 Scenario: You are managing a small train station. You want to find out the minimum number of platforms needed so that no train has to wait.Each train has an arrival time and a departure time.

🎯 Goal: Build a Java program that calculates the minimum number of platforms required for the trains so that none of them have to wait.

📋 What You'll Learn

Create two arrays called arrivals and departures with exact train times

Create an integer variable called platforms_needed to count platforms

Use a loop to find the minimum number of platforms needed

Print the final number of platforms needed

💡 Why This Matters

🌍 Real World

Train stations and airports use this logic to manage platforms or gates so that vehicles do not wait and operations run smoothly.

💼 Career

This problem is common in scheduling and resource allocation tasks in software engineering and operations research.

1

Create train arrival and departure arrays

Create two integer arrays called arrivals and departures with these exact values:
arrivals = new int[]{900, 940, 950, 1100, 1500, 1800};
departures = new int[]{910, 1200, 1120, 1130, 1900, 2000};

DSA Java

// Create arrivals and departures arrays with exact values
// Your code here

Hint

Use int[] arrivals = new int[]{...}; and int[] departures = new int[]{...}; with the exact times given.

2

Create a variable to count platforms needed

Create an integer variable called platforms_needed and set it to 1 to start counting platforms.

DSA Java

int[] arrivals = new int[]{900, 940, 950, 1100, 1500, 1800};
int[] departures = new int[]{910, 1200, 1120, 1130, 1900, 2000};
// Create platforms_needed variable and set to 1
// Your code here

Hint

Use int platforms_needed = 1; to start counting platforms.

3

Calculate minimum platforms needed

Sort the arrivals and departures arrays using Arrays.sort(). Then use two integer variables i and j starting at 1 and 0 respectively. Use a while loop to compare arrivals[i] and departures[j]. If arrivals[i] <= departures[j], increase platforms_needed by 1 and i by 1. Otherwise, decrease platforms_needed by 1 and increase j by 1. Continue until i reaches the length of arrivals.

DSA Java

import java.util.Arrays;

int[] arrivals = new int[]{900, 940, 950, 1100, 1500, 1800};
int[] departures = new int[]{910, 1200, 1120, 1130, 1900, 2000};
int platforms_needed = 1;
// Sort arrivals and departures
// Use i=1, j=0 and while loop to update platforms_needed
// Your code here

Hint

Sort both arrays first. Use two pointers i and j to compare arrivals and departures. Increase or decrease platforms_needed accordingly.

4

Print the minimum number of platforms needed

Print the integer variable max_platforms using System.out.println(max_platforms); to show the minimum number of platforms needed.

DSA Java

import java.util.Arrays;

int[] arrivals = new int[]{900, 940, 950, 1100, 1500, 1800};
int[] departures = new int[]{910, 1200, 1120, 1130, 1900, 2000};
int platforms_needed = 1;

Arrays.sort(arrivals);
Arrays.sort(departures);

int i = 1, j = 0;
int max_platforms = 1;

while (i  max_platforms) {
            max_platforms = platforms_needed;
        }
    } else {
        platforms_needed--;
        j++;
    }
}
// Print the max_platforms
// Your code here

Hint

Use System.out.println(max_platforms); to print the final answer.

Practice

1. What does the "Minimum Number of Platforms" problem ask you to find given train arrival and departure times?

easy

A. The least number of platforms needed so no train waits

B. The total number of trains arriving in a day

C. The longest time a train stays on a platform

D. The earliest train arrival time

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of platforms required so that no train has to wait for another to leave.

2. Step 2: Clarify what is being counted

   We count how many trains overlap in time on the station to find the minimum platforms needed.

3. Final Answer:

   The least number of platforms needed so no train waits -> Option A

4. Quick Check:

   Minimum platforms = max trains overlapping [OK]

Hint: Count overlapping trains to find minimum platforms needed [OK]

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping times
• Counting earliest arrival only

2. Which Java data structure is best suited to efficiently find the minimum number of platforms needed given sorted arrival and departure arrays?

easy

A. PriorityQueue (Min-Heap)

B. Stack

C. LinkedList

D. HashMap

Solution

1. Step 1: Identify the need for quick minimum departure tracking

   We need to know the earliest train departure to free a platform, so a min-heap helps track minimum departure time efficiently.

2. Step 2: Match data structure to problem

   PriorityQueue in Java is a min-heap, perfect for this use case to manage platforms dynamically.

3. Final Answer:

   PriorityQueue (Min-Heap) -> Option A

4. Quick Check:

   Min-heap tracks earliest departure [OK]

Hint: Use min-heap to track earliest departure times [OK]

Common Mistakes:

• Using HashMap which doesn't maintain order
• Using Stack which is LIFO, not suitable
• Using LinkedList which is inefficient for min queries

3. What is the output of the following Java code snippet that calculates minimum platforms?

int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
System.out.println(minPlatforms(arrivals, departures));

// Assume minPlatforms returns the minimum platforms needed

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Sort arrival and departure times

   Arrivals: 900, 940, 950, 1100, 1500, 1800 Departures: 910, 1120, 1130, 1200, 1900, 2000

2. Step 2: Count overlapping trains

   At 900-910: 1 train At 940-1120: 2 trains overlap At 950-1130: 3 trains overlap (max) After 1130, trains start leaving, so max platforms needed = 3

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Max overlap = 3 platforms [OK]

Hint: Find max overlapping intervals after sorting [OK]

Common Mistakes:

• Not sorting times before processing
• Counting total trains instead of overlaps
• Mixing arrival and departure arrays

4. Identify the bug in this Java method to find minimum platforms:

public static int minPlatforms(int[] arr, int[] dep) {
    Arrays.sort(arr);
    Arrays.sort(dep);
    int i = 0, j = 0, platforms = 0, maxPlatforms = 0;
    while (i < arr.length && j < dep.length) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
        } else {
            platforms--;
            j++;
        }
        maxPlatforms = Math.max(maxPlatforms, platforms);
    }
    return maxPlatforms;
}

medium

A. The loop should run while i < arr.length only

B. The condition should be arr[i] < dep[j] instead of <= to avoid counting simultaneous arrival and departure

C. The platforms variable should not be decremented

D. Arrays.sort should be called only on arrivals

Solution

1. Step 1: Analyze the comparison condition

   The condition arr[i] <= dep[j] counts a train arriving exactly when another departs as overlapping, increasing platforms unnecessarily.

2. Step 2: Correct the condition to avoid overcounting

   Changing to arr[i] < dep[j] treats simultaneous arrival and departure as no overlap, which is correct for platform counting.

3. Final Answer:

   The condition should be arr[i] < dep[j] instead of <= to avoid counting simultaneous arrival and departure -> Option B

4. Quick Check:

   Use strict less than for arrival vs departure [OK]

Hint: Use < not <= to avoid counting simultaneous arrival and departure [OK]

Common Mistakes:

• Using <= causes overcounting platforms
• Not sorting both arrays
• Incorrect loop condition

5. Given arrival times [1000, 1010, 1025, 1030, 1040] and departure times [1020, 1035, 1045, 1050, 1100], what is the minimum number of platforms needed if trains arriving exactly when another departs do NOT require a new platform?

hard

A. 4

B. 5

C. 2

D. 3

Solution

1. Step 1: Sort and analyze arrival and departure times

   Arrivals: 1000, 1010, 1025, 1030, 1040 Departures: 1020, 1035, 1045, 1050, 1100

2. Step 2: Count overlapping trains considering no extra platform if arrival equals departure

   1000-1020: 1 train 1010-1035: overlaps with first, total 2 1025-1045: first gone at 1020, overlaps with second, total 2 1030-1050: overlaps with second (till 1035) and third (till 1045), total 3 1040-1100: second gone at 1035, overlaps with third, fourth, total 3 (max)

3. Step 3: Adjust for arrival equals departure rule

   No arrivals equal departures here, so max platforms = 3

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Max overlap = 3 platforms [OK]

Hint: Count overlaps, exclude equal arrival and departure as overlap [OK]

Common Mistakes:

• Counting equal arrival and departure as overlap
• Not sorting times
• Miscounting overlaps