Loading…

mediumGreedySometimes asked

Minimum Number of Platforms

Q: How do you solve Minimum Number of Platforms using the Pairwise Overlap Count (Baseline) approach?

When to use it: Start here to anchor the definition — the answer is the peak overlap — then optimise away the quadratic pair comparison. Directly count concurrency. For each train `i`, count how many trains are present at the instant train `i` arrives — that is, how many trains `j` satisfy `arr[j] <= arr[i] <= dep[j]` (train `j` arrived at or before `i` and hasn't departed). The maximum of these counts over all `i` is the minimum number of platforms. **Why the peak occurs at some arrival instant.** Concurrency only ever *increases* at an arrival; departures lower it. So the maximum number of simultaneous trains is reached right when some train arrives, never strictly between events. That means checking the overlap count at each arrival instant is enough — we don't need to test arbitrary times. **Why the answer is the peak, not the total.** A platform can be reused once a train leaves, so the total number of trains over the day is irrelevant. What forces you to build more platforms is the single busiest instant — the largest pile-up of overlapping intervals. That maximum overlap is exactly the resource you must provision. **Why we don't ship this.** Counting overlaps by comparing every train against every other is `O(n²)`. For `n = 10⁵` that's `10¹⁰` comparisons — far too slow. The waste is that we recompute overlap from scratch at each arrival. The optimal approach instead processes arrivals and departures in time order and keeps a running balance, so each event is handled once. Time complexity: O(n²). Space complexity: O(1).

Greedy Algorithms · 15 of 23 · 10 min

You are given two arrays, arr and dep, of size n, where arr[i] and dep[i] are the arrival and departure times of the i-th train at a station (with arr[i] ≤ dep[i]). A platform can hold at most one train at a time, and a train occupies a platform for the whole closed interval [arr[i], dep[i]].

Return the **minimum number of platforms** needed so that no train ever waits. By convention, if one train departs at the exact moment another arrives, they **cannot** share a platform.

In plain English

Each train is a closed time interval. A platform is busy for the whole interval, so the number of platforms you need at any instant equals the number of intervals covering that instant. The minimum number of platforms is therefore the maximum, over all instants, of how many intervals overlap — the peak concurrency. We find that peak by walking through arrival and departure events in time order.

Examples

Example 1

Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Note: Around 11:00–11:20 three trains (the 9:40, 9:50, and 11:00 arrivals) overlap before any of them leaves — the peak is 3.

Example 2

Input: arr = [900, 1100, 1235], dep = [1000, 1200, 1240]
Output: 1
Note: Each train departs before the next arrives, so they never overlap — one platform suffices.

Example 3

Input: arr = [1000, 1000], dep = [1100, 1100]
Output: 2
Note: Both trains are present for the same hour — two platforms required.

Constraints

1 ≤ n ≤ 10⁵
Times are given in a comparable format (e.g. integers like 900 for 09:00, or minutes since midnight)
arr[i] ≤ dep[i] for every train
A train arriving exactly when another departs needs its own platform (arrival-first tie rule)

Clarifying questions4First question: If a train departs at exactly the time another arrives, can they share a platform?Explore questions

Q1.If a train departs at exactly the time another arrives, can they share a platform?
By the standard convention, no — the arriving train needs its own platform that instant. That's why the tie test is arr <= dep (arrival counted before that departure frees up).
Q2.Are the arrival and departure arrays already sorted?
Not necessarily. I sort each independently; that decoupling is the key step and it doesn't matter that a train's own arrival and departure end up in different positions.
Q3.Do arrivals and departures pair up by index after sorting?
No, and they don't need to. We only count how many trains are present, never which specific train — so breaking the pairing is safe.
Q4.Can times wrap past midnight?
I'll assume all times are within a single day and comparable as given. If they wrapped, I'd normalise to minutes since a fixed origin first.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The answer is the maximum number of trains present at the station at any single instant. Sort the arrival times and departure times into two separate sorted arrays, then sweep them with two pointers: every time the next event is an arrival, a train comes in (platforms++); every time it's a departure, one leaves (platforms--). Track the running peak. Sorting dominates at O(n log n); the sweep is O(n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe 'minimum platforms' as 'maximum simultaneous overlap', and realise you can sort arrivals and departures independently and sweep them, instead of comparing every pair of trains.

Where candidates slip

Keeping arrivals paired with their own departures, comparing every pair O(n²), or mishandling the arr == dep tie so two trains 'share' a platform that they actually can't.

How to stand out

Say 'the answer is the peak concurrency, so I'll sort starts and ends separately and sweep — a balance that goes up on arrivals and down on departures'. Then nail the tie convention explicitly and connect it to Meeting Rooms II.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Pairwise Overlap Count (Baseline)	`O(n²)`	`O(1)`	Start here to anchor the definition — the answer is the peak overlap — then optimise away the quadratic pair comparison.	Read
2	Sort + Two-Pointer Sweep (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Phrase it as 'sort arrivals and departures separately, then sweep a +1/-1 balance in time order'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMin platforms = peak simultaneous trainsHow to find the peak overlap?Compare every pairSort events, sweepExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Pairwise Overlap Count (Baseline)

TimeO(n²)SpaceO(1)

Start here to anchor the definition — the answer is the peak overlap — then optimise away the quadratic pair comparison.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You need the largest number of trains present at the same time. For one chosen train, how many others are present during its stay?

2Hint 2Explore hint

Two intervals [a1,d1] and [a2,d2] overlap when a1 <= d2 AND a2 <= d1. Count, for each train, how many trains overlap the moment it arrives.

3Hint 3Explore hint

Take the maximum of those counts. That maximum is the minimum number of platforms. It's two nested loops — correct, but O(n²).

A · Core idea

Directly count concurrency. For each train i, count how many trains are present at the instant train i arrives — that is, how many trains j satisfy arr[j] <= arr[i] <= dep[j] (train j arrived at or before i and hasn't departed). The maximum of these counts over all i is the minimum number of platforms.

Why the peak occurs at some arrival instant. Concurrency only ever increases at an arrival; departures lower it. So the maximum number of simultaneous trains is reached right when some train arrives, never strictly between events. That means checking the overlap count at each arrival instant is enough — we don't need to test arbitrary times.

Why the answer is the peak, not the total. A platform can be reused once a train leaves, so the total number of trains over the day is irrelevant. What forces you to build more platforms is the single busiest instant — the largest pile-up of overlapping intervals. That maximum overlap is exactly the resource you must provision.

Why we don't ship this. Counting overlaps by comparing every train against every other is O(n²). For n = 10⁵ that's 10¹⁰ comparisons — far too slow. The waste is that we recompute overlap from scratch at each arrival. The optimal approach instead processes arrivals and departures in time order and keeps a running balance, so each event is handled once.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [900, 940, 950], dep = [910, 1200, 1120]

i=0 (arr 900)

only train0 present (900 in [900,910])

Statecount=1, max=1

Final result2

C · Code with teaching comments

Reference implementation previewpublic int minPlatforms(int[] arr, int[] dep) { int n = arr.length; int peak = 0; for (int i = 0; i < n; i++) { int present = 0;Explore the full code

solution.javaJava

Pairwise Overlap Count (Baseline) — reference

2 teaching notes

1
public int minPlatforms(int[] arr, int[] dep) {
2
    int n = arr.length;
3
    int peak = 0;
4
    for (int i = 0; i < n; i++) {
5
        int present = 0;
6
        for (int j = 0; j < n; j++) {
7
            // Train j is present at the instant train i arrives.
8
            // Train j is on a platform at time arr[i] if it arrived no later and hasn't
9
            // departed yet.
10
            if (arr[j] <= arr[i] && arr[i] <= dep[j]) {
11
                present++;
12
            }
13
        }
14
        // The busiest arrival instant determines how many platforms are needed.
15
        peak = Math.max(peak, present);
16
    }
17
    return peak;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Concurrency rises only at arrivals, so the peak is some arrival instant — that observation is what later lets us sweep events in time order instead of comparing pairs. The O(n²) is purely the cost of recomputing overlaps independently for each train.

ComplexityO(n²) time, O(1) space — For each of n trains we scan all n trains to count overlaps at its arrival instant → O(n²) time. We keep only a running max → O(1) extra space.

E · Edge cases and pitfalls5single train — Only itself is present at its arrival → peak 1.Explore edge cases

Edge cases handled

single trainOnly itself is present at its arrival → peak 1.
no overlapsEach arrival sees only its own train present → peak 1.

Pitfalls

Returning the total number of trains instead of the peak overlap.
Checking only arr[i] without the dep[j] bound — counts trains that already left.
Treating this as too trivial to mention — stating 'the answer is the peak overlap' is the framing the interviewer wants.

03.2

Approach 2 of 2 · Optimal

Sort + Two-Pointer Sweep (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Phrase it as 'sort arrivals and departures separately, then sweep a +1/-1 balance in time order'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The peak overlap changes only at events (an arrival or a departure). What if you processed all events in time order and kept a running count?

2Hint 2Explore hint

Sort arrivals ascending and departures ascending into two separate arrays — you don't need to know which train is which, only how many are present.

3Hint 3Explore hint

Walk both arrays with pointers i (arrivals) and j (departures). If the next arrival is at or before the next departure, a train comes in (count++, update peak); otherwise one leaves (count--). Stop when all arrivals are processed.

A · Core idea

Sort the arrival times and the departure times into two separate ascending arrays. Use two pointers, i over arrivals and j over departures, and a running platforms count. At each step compare the next arrival with the next departure: if the arrival is earlier or equal, a train enters (platforms++, advance i, update the peak); otherwise the earliest still-occupied train leaves (platforms--, advance j). Continue until every arrival is consumed. The peak platforms value is the answer.

Why decoupling arrivals from departures is legal. We never care which train is on a platform, only how many are. So we can sort all arrivals together and all departures together, even though that splits each train's own pair into two different arrays. The merge of these two sorted streams reconstructs the timeline of events in order, which is all the count depends on.

Why the two-pointer merge gives the right balance. Sweeping the two sorted arrays in lockstep is a merge: at each moment we handle the chronologically next event. An arrival pushes the concurrent count up; a departure pulls it down. Because concurrency peaks only on arrivals, we check the peak right after each platforms++. When the last arrival is processed, no later event can raise the count, so we can stop — remaining departures only lower it.

Why the tie rule is `arr[i] <= dep[j]`. If a train arrives at the exact instant another departs and they cannot share a platform, the arrival must be counted before the departure frees its slot. Using <= processes the arrival first, so the count momentarily includes both — correctly demanding a separate platform. If the problem said they could share, you'd flip to < (process the departure first).

Why this is optimal. Each event is handled exactly once after the sort, so the sweep is linear and sorting dominates. There's no way to know the peak overlap without at least ordering the events, so O(n log n) is the natural bound (unless times are small bounded integers, where a difference array hits O(n + maxTime)).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [900, 940, 950, 1100], dep = [910, 1200, 1120, 1130]

Interactive diagram

Running balance over the event timeline

arr 900 ≤ dep 910

Active call / nodeSupporting contextReturned stateNot active

Each arrival +1, each departure −1. The peak (3) is the minimum platforms. Events in time order for the worked example.

Final result3

C · Code with teaching comments

solution.javaJava

Sort + Two-Pointer Sweep (Optimal) — optimal

4 teaching notes

1
public int minPlatforms(int[] arr, int[] dep) {
2
    int n = arr.length;
3
    Arrays.sort(arr);
4
    Arrays.sort(dep);
5
    int i = 0, j = 0;
6
    int platforms = 0, peak = 0;
7
    // Stop once all arrivals are processed; later departures can only lower the count.
8
    while (i < n) {
9
        // Arrival-first tie rule: at equal times the arriving train needs its own
10
        // platform.
11
        if (arr[i] <= dep[j]) {
12
            platforms++;            // a train arrives
13
            // Update peak only on arrivals — that's when concurrency can rise.
14
            peak = Math.max(peak, platforms);
15
            i++;
16
        } else {
17
            platforms--;            // the earliest occupied train leaves
18
            j++;
19
        }
20
    }
21
    return peak;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Decoupling each interval's start from its end and sorting them separately is the sweep-line trick: a sorted merge of starts and ends reduces 'maximum overlap' to a running +1/-1 balance. It generalises directly to Meeting Rooms II and any peak-concurrency question.

ComplexityO(n log n) time, O(1) space — Sorting the two arrays is O(n log n). The sweep advances i or j every step and stops after the last arrival, so it's O(n). Only a few counters → O(1) extra space.

E · Edge cases and pitfalls6all trains overlap — Every arrival precedes every departure → platforms climbs to n → peak n.Explore edge cases

Edge cases handled

all trains overlapEvery arrival precedes every departure → platforms climbs to n → peak n.
arr == dep across trainsWith the <= rule, an arrival at a departure instant still bumps the count, demanding a separate platform.
single trainOne arrival processed → platforms 1 → peak 1.

Pitfalls

Keeping arrivals paired with their own departures instead of sorting the two arrays separately.
Using arr[i] < dep[j] when the convention says an arrival and a departure at the same time can't share — flips the tie wrongly.
Updating the peak on departures too — harmless to the max but signals a muddled mental model.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int minPlatforms(int[] arr, int[] dep) { int n = arr.length; Arrays.sort(arr); Arrays.sort(dep); int i = 0, j = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting total trains, not peak overlap

Platforms are reusable once a train leaves, so the answer is the busiest instant, not the day's train count. Returning n hugely overestimates.

Explore the code comparison

Don't write this

return len(arr)            # total trains, ignores reuse

Write this instead

# sweep and track the maximum concurrent count
return peak

Wrong tie handling

If an arrival at the same time as a departure cannot share a platform, the arrival must be counted before the departure frees up. Using < processes the departure first and undercounts by one at ties.

Explore the code comparison

Don't write this

if (arr[i] < dep[j]) {     // departure wins ties → shares a platform
    platforms++; i++;
}

Write this instead

if (arr[i] <= dep[j]) {    // arrival wins ties → its own platform
    platforms++; i++;
}

Sorting arrivals but reusing original departures

If you sort arr but compare against dep in original order, the departure pointer no longer tracks the earliest still-occupied train and the balance becomes nonsense. Sort BOTH.

Explore the code comparison

Don't write this

arr.sort()                 # dep left unsorted
# ... compare arr[i] <= dep[j] with unsorted dep

Write this instead

arr.sort()
dep.sort()

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort arrivals and departures separately, two-pointer sweep, track peak overlap

Code pattern to memorize

sort(arr); sort(dep)
i = j = 0; platforms = 0; peak = 0
while i < n:
    if arr[i] <= dep[j]:
        platforms++; i++          # a train arrives
        peak = max(peak, platforms)
    else:
        platforms--; j++          # a train departs
return peak

Rules to remember

1The answer is the maximum simultaneous overlap of the time intervals — not the total number of trains.
2Sort arrivals and departures into two independent sorted arrays; you deliberately break the pairing between a train's own arrival and departure.
3On a tie (arr[i] == dep[j]), decide whether a train can arrive the instant another leaves. The common convention is arrival counts first (needs its own platform), so use arr[i] <= dep[j].
4Only update the peak on an arrival — departures never raise the count.
5It's the same idea as a sweep line / 'meeting rooms' overlap count.

Use this pattern when

Count the maximum number of overlapping intervals at any point in time
Resource sizing: how many rooms / platforms / servers handle peak concurrency
Events have a start and an end and you care about simultaneous activity
You can decouple starts from ends and process them in time order

Choose another pattern when

You must keep each interval's start tied to its own end → don't decouple; use a different model
You need WHICH intervals overlap, not just how many → interval tree / sweep with IDs
Intervals are weighted and you optimise a sum → weighted interval scheduling DP
Times are tiny bounded integers → a difference array over time can beat sorting

Interview takeaway

Minimum Platforms is the overlap-count sweep in disguise: sort starts and ends separately, walk them in time order, and the running balance's peak is the answer. Decoupling each train's arrival from its departure is the move people miss — once you do, it's a clean two-pointer merge. Same engine as Meeting Rooms II.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical maximum-overlap sweep line. Recognise it whenever you must size a resource for peak concurrency of start/end intervals: sort starts and ends separately, walk them in time order, and the peak of the +1/-1 balance is the answer. Same engine as Meeting Rooms II.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Meeting Rooms II
Coming soon
Identical peak-overlap count — minimum rooms is the same two-pointer (or min-heap of end times) sweep.
Meeting Rooms
Coming soon
Just ask whether peak overlap ever exceeds 1 — a yes/no version of the same sweep.
Maximum Population Year
Coming soon
Peak overlap of birth–death intervals over small bounded years — difference array beats sorting.
Merge Intervals
Coming soon
Related interval-sweep skill; here you coalesce overlapping ranges rather than count them.

Same pattern

←

Huffman Encoding

Continue · Next problem

Beautiful Pairs

mediumGreedySometimes asked

Minimum Number of Platforms

Greedy Algorithms · 15 of 23 · 10 min

Return the **minimum number of platforms** needed so that no train ever waits. By convention, if one train departs at the exact moment another arrives, they **cannot** share a platform.

In plain English

Examples

Example 1

Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Note: Around 11:00–11:20 three trains (the 9:40, 9:50, and 11:00 arrivals) overlap before any of them leaves — the peak is 3.

Example 2

Input: arr = [900, 1100, 1235], dep = [1000, 1200, 1240]
Output: 1
Note: Each train departs before the next arrives, so they never overlap — one platform suffices.

Example 3

Input: arr = [1000, 1000], dep = [1100, 1100]
Output: 2
Note: Both trains are present for the same hour — two platforms required.

Constraints

1 ≤ n ≤ 10⁵
Times are given in a comparable format (e.g. integers like 900 for 09:00, or minutes since midnight)
arr[i] ≤ dep[i] for every train
A train arriving exactly when another departs needs its own platform (arrival-first tie rule)

Clarifying questions4First question: If a train departs at exactly the time another arrives, can they share a platform?Explore questions

Q1.If a train departs at exactly the time another arrives, can they share a platform?
By the standard convention, no — the arriving train needs its own platform that instant. That's why the tie test is arr <= dep (arrival counted before that departure frees up).
Q2.Are the arrival and departure arrays already sorted?
Not necessarily. I sort each independently; that decoupling is the key step and it doesn't matter that a train's own arrival and departure end up in different positions.
Q3.Do arrivals and departures pair up by index after sorting?
No, and they don't need to. We only count how many trains are present, never which specific train — so breaking the pairing is safe.
Q4.Can times wrap past midnight?
I'll assume all times are within a single day and comparable as given. If they wrapped, I'd normalise to minutes since a fixed origin first.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe 'minimum platforms' as 'maximum simultaneous overlap', and realise you can sort arrivals and departures independently and sweep them, instead of comparing every pair of trains.

Where candidates slip

Keeping arrivals paired with their own departures, comparing every pair O(n²), or mishandling the arr == dep tie so two trains 'share' a platform that they actually can't.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Pairwise Overlap Count (Baseline)	`O(n²)`	`O(1)`	Start here to anchor the definition — the answer is the peak overlap — then optimise away the quadratic pair comparison.	Read
2	Sort + Two-Pointer Sweep (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Phrase it as 'sort arrivals and departures separately, then sweep a +1/-1 balance in time order'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Pairwise Overlap Count (Baseline)

TimeO(n²)SpaceO(1)

Start here to anchor the definition — the answer is the peak overlap — then optimise away the quadratic pair comparison.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You need the largest number of trains present at the same time. For one chosen train, how many others are present during its stay?

2Hint 2Explore hint

Two intervals [a1,d1] and [a2,d2] overlap when a1 <= d2 AND a2 <= d1. Count, for each train, how many trains overlap the moment it arrives.

3Hint 3Explore hint

Take the maximum of those counts. That maximum is the minimum number of platforms. It's two nested loops — correct, but O(n²).

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [900, 940, 950], dep = [910, 1200, 1120]

i=0 (arr 900)

only train0 present (900 in [900,910])

Statecount=1, max=1

Final result2

C · Code with teaching comments

Reference implementation previewpublic int minPlatforms(int[] arr, int[] dep) { int n = arr.length; int peak = 0; for (int i = 0; i < n; i++) { int present = 0;Explore the full code

solution.javaJava

Pairwise Overlap Count (Baseline) — reference

2 teaching notes

1
public int minPlatforms(int[] arr, int[] dep) {
2
    int n = arr.length;
3
    int peak = 0;
4
    for (int i = 0; i < n; i++) {
5
        int present = 0;
6
        for (int j = 0; j < n; j++) {
7
            // Train j is present at the instant train i arrives.
8
            // Train j is on a platform at time arr[i] if it arrived no later and hasn't
9
            // departed yet.
10
            if (arr[j] <= arr[i] && arr[i] <= dep[j]) {
11
                present++;
12
            }
13
        }
14
        // The busiest arrival instant determines how many platforms are needed.
15
        peak = Math.max(peak, present);
16
    }
17
    return peak;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — For each of n trains we scan all n trains to count overlaps at its arrival instant → O(n²) time. We keep only a running max → O(1) extra space.

E · Edge cases and pitfalls5single train — Only itself is present at its arrival → peak 1.Explore edge cases

Edge cases handled

single trainOnly itself is present at its arrival → peak 1.
no overlapsEach arrival sees only its own train present → peak 1.

Pitfalls

Returning the total number of trains instead of the peak overlap.
Checking only arr[i] without the dep[j] bound — counts trains that already left.
Treating this as too trivial to mention — stating 'the answer is the peak overlap' is the framing the interviewer wants.

03.2

Approach 2 of 2 · Optimal

Sort + Two-Pointer Sweep (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Phrase it as 'sort arrivals and departures separately, then sweep a +1/-1 balance in time order'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The peak overlap changes only at events (an arrival or a departure). What if you processed all events in time order and kept a running count?

2Hint 2Explore hint

Sort arrivals ascending and departures ascending into two separate arrays — you don't need to know which train is which, only how many are present.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [900, 940, 950, 1100], dep = [910, 1200, 1120, 1130]

Interactive diagram

Running balance over the event timeline

arr 900 ≤ dep 910

Active call / nodeSupporting contextReturned stateNot active

Each arrival +1, each departure −1. The peak (3) is the minimum platforms. Events in time order for the worked example.

Final result3

C · Code with teaching comments

solution.javaJava

Sort + Two-Pointer Sweep (Optimal) — optimal

4 teaching notes

1
public int minPlatforms(int[] arr, int[] dep) {
2
    int n = arr.length;
3
    Arrays.sort(arr);
4
    Arrays.sort(dep);
5
    int i = 0, j = 0;
6
    int platforms = 0, peak = 0;
7
    // Stop once all arrivals are processed; later departures can only lower the count.
8
    while (i < n) {
9
        // Arrival-first tie rule: at equal times the arriving train needs its own
10
        // platform.
11
        if (arr[i] <= dep[j]) {
12
            platforms++;            // a train arrives
13
            // Update peak only on arrivals — that's when concurrency can rise.
14
            peak = Math.max(peak, platforms);
15
            i++;
16
        } else {
17
            platforms--;            // the earliest occupied train leaves
18
            j++;
19
        }
20
    }
21
    return peak;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6all trains overlap — Every arrival precedes every departure → platforms climbs to n → peak n.Explore edge cases

Edge cases handled

all trains overlapEvery arrival precedes every departure → platforms climbs to n → peak n.
arr == dep across trainsWith the <= rule, an arrival at a departure instant still bumps the count, demanding a separate platform.
single trainOne arrival processed → platforms 1 → peak 1.

Pitfalls

Keeping arrivals paired with their own departures instead of sorting the two arrays separately.
Using arr[i] < dep[j] when the convention says an arrival and a departure at the same time can't share — flips the tie wrongly.
Updating the peak on departures too — harmless to the max but signals a muddled mental model.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int minPlatforms(int[] arr, int[] dep) { int n = arr.length; Arrays.sort(arr); Arrays.sort(dep); int i = 0, j = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting total trains, not peak overlap

Platforms are reusable once a train leaves, so the answer is the busiest instant, not the day's train count. Returning n hugely overestimates.

Explore the code comparison

Don't write this

return len(arr)            # total trains, ignores reuse

Write this instead

# sweep and track the maximum concurrent count
return peak

Wrong tie handling

If an arrival at the same time as a departure cannot share a platform, the arrival must be counted before the departure frees up. Using < processes the departure first and undercounts by one at ties.

Explore the code comparison

Don't write this

if (arr[i] < dep[j]) {     // departure wins ties → shares a platform
    platforms++; i++;
}

Write this instead

if (arr[i] <= dep[j]) {    // arrival wins ties → its own platform
    platforms++; i++;
}

Sorting arrivals but reusing original departures

If you sort arr but compare against dep in original order, the departure pointer no longer tracks the earliest still-occupied train and the balance becomes nonsense. Sort BOTH.

Explore the code comparison

Don't write this

arr.sort()                 # dep left unsorted
# ... compare arr[i] <= dep[j] with unsorted dep

Write this instead

arr.sort()
dep.sort()

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort arrivals and departures separately, two-pointer sweep, track peak overlap

Code pattern to memorize

sort(arr); sort(dep)
i = j = 0; platforms = 0; peak = 0
while i < n:
    if arr[i] <= dep[j]:
        platforms++; i++          # a train arrives
        peak = max(peak, platforms)
    else:
        platforms--; j++          # a train departs
return peak

Rules to remember

1The answer is the maximum simultaneous overlap of the time intervals — not the total number of trains.
2Sort arrivals and departures into two independent sorted arrays; you deliberately break the pairing between a train's own arrival and departure.
3On a tie (arr[i] == dep[j]), decide whether a train can arrive the instant another leaves. The common convention is arrival counts first (needs its own platform), so use arr[i] <= dep[j].
4Only update the peak on an arrival — departures never raise the count.
5It's the same idea as a sweep line / 'meeting rooms' overlap count.

Use this pattern when

Count the maximum number of overlapping intervals at any point in time
Resource sizing: how many rooms / platforms / servers handle peak concurrency
Events have a start and an end and you care about simultaneous activity
You can decouple starts from ends and process them in time order

Choose another pattern when

You must keep each interval's start tied to its own end → don't decouple; use a different model
You need WHICH intervals overlap, not just how many → interval tree / sweep with IDs
Intervals are weighted and you optimise a sum → weighted interval scheduling DP
Times are tiny bounded integers → a difference array over time can beat sorting

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Meeting Rooms II
Coming soon
Identical peak-overlap count — minimum rooms is the same two-pointer (or min-heap of end times) sweep.
Meeting Rooms
Coming soon
Just ask whether peak overlap ever exceeds 1 — a yes/no version of the same sweep.
Maximum Population Year
Coming soon
Peak overlap of birth–death intervals over small bounded years — difference array beats sorting.
Merge Intervals
Coming soon
Related interval-sweep skill; here you coalesce overlapping ranges rather than count them.

Same pattern

←

Huffman Encoding

Continue · Next problem

Beautiful Pairs