Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogleMicrosoft

Minimum Number of Platforms Required

Choose your preparation mode4 modes available
▶
Steps
setup

Create arrival events

We start by creating events for each arrival time, marking them with +1 to indicate a train arriving.

💡 Separating arrivals as +1 events helps us later count how many trains are currently at the station.
Line:for time in arrivals: events.append((time, 1)) # arrival
💡 Each arrival increases the platform requirement by one when processed.
📊
Minimum Number of Platforms Required - Watch the Algorithm Execute, Step by Step
Watching the algorithm process each event one by one reveals how overlapping intervals cause platform requirements to increase and decrease, making the concept of sweep line intuitive.
Step 1/17
·Active fill★Answer cell
insert
i
(900,1)
0
(940,1)
1
(950,1)
2
(1100,1)
3
(1500,1)
4
(1800,1)
5
Result: "events = [(900,1), (940,1), (950,1), (1100,1), (1500,1), (1800,1)]"
insert
(900,1)
0
(940,1)
1
(950,1)
2
(1100,1)
3
(1500,1)
4
(1800,1)
5
i
(910,-1)
6
(1200,-1)
7
(1120,-1)
8
(1130,-1)
9
(1900,-1)
10
(2000,-1)
11
Result: "events = arrivals + departures (unsorted)"
sort
i
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "events sorted by time and type"
initialize
i
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=0, max_platforms=0"
compare
i
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=1, max_platforms=1"
compare
(900,1)
0
i
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=0, max_platforms=1"
compare
(900,1)
0
(910,-1)
1
i
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=1, max_platforms=1"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
i
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=2, max_platforms=2"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
i
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=3, max_platforms=3"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
i
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=2, max_platforms=3"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
i
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=1, max_platforms=3"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
i
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=0, max_platforms=3"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
i
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=1, max_platforms=3"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
i
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=2, max_platforms=3"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
i
(1900,-1)
10
(2000,-1)
11
Result: "platforms_needed=1, max_platforms=3"
compare
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
i
(2000,-1)
11
Result: "platforms_needed=0, max_platforms=3"
record
(900,1)
0
(910,-1)
1
(940,1)
2
(950,1)
3
(1100,1)
4
(1120,-1)
5
(1130,-1)
6
(1200,-1)
7
(1500,1)
8
(1800,1)
9
(1900,-1)
10
(2000,-1)
11
Result: 3

Key Takeaways

✓ Sorting events by time and prioritizing departures before arrivals at the same time is crucial.

This prevents overcounting platforms when trains arrive and depart simultaneously, which is not obvious from code alone.

✓ The sweep line approach converts interval overlap into a simple running count problem.

Visualizing events as points on a timeline helps understand how overlaps translate to platform needs.

✓ Tracking both current platforms needed and maximum platforms needed separately is essential.

The maximum platforms needed is the final answer, but the current count fluctuates as events are processed.

Practice

(1/5)
1. Given the following code for inserting an interval, what is the final returned list after calling insert([[1,3],[6,9]], [2,5])?
from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    return merged
easy
A. [[1,5],[6,9]]
B. [[1,3],[2,5],[6,9]]
C. [[1,3],[6,9],[2,5]]
D. [[1,9]]

Solution

  1. Step 1: Append and sort intervals

    After appending [2,5], intervals become [[1,3],[6,9],[2,5]]. Sorting by start time yields [[1,3],[2,5],[6,9]].
  2. Step 2: Merge overlapping intervals

    Start with merged = [[1,3]]. The next interval [2,5] overlaps since 2 <= 3, so merge to [1,5]. Next interval [6,9] does not overlap, so append it.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Result matches expected merged intervals [OK]
Hint: Sort after insertion, then merge overlapping intervals [OK]
Common Mistakes:
  • Not sorting after insertion leads to wrong order
  • Failing to merge intervals that overlap at boundaries
  • Appending newInterval multiple times
2. Consider the following Python function implementing the binary search approach for the minimum interval problem. Given intervals = [[1,4],[2,4],[3,6]] and queries = [2,5], what is the output of the function call min_interval_binary_search(intervals, queries)?
easy
A. [3, 4]
B. [3, 4]
C. [3, 4]
D. [3, 4]

Solution

  1. Step 1: Sort intervals by length

    Intervals sorted by length: [2,4] length=3, [1,4] length=4, [3,6] length=4.
  2. Step 2: Binary search for each query

    Query=2: smallest interval covering 2 is length=3 ([2,4]). Query=5: smallest interval covering 5 is length=4 ([3,6]).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Output matches expected minimal interval lengths for queries [OK]
Hint: Trace binary search narrowing on interval lengths [OK]
Common Mistakes:
  • Off-by-one in interval length calculation
  • Incorrect binary search boundaries
  • Confusing start and end indices
3. Examine the following buggy code for interval intersections:
def intervalIntersection(A, B):
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] <= B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result
What is the bug in this code?
medium
A. The condition 'if A[i][1] <= B[j][0]' should use '<' instead of '<=' to correctly detect touching intervals.
B. The pointer increments inside the else block are reversed; they should increment the pointer with the larger endpoint.
C. The overlap condition should check 'start < end' instead of 'start <= end' to avoid zero-length intervals.
D. The code does not handle empty input lists, which can cause runtime errors.

Solution

  1. Step 1: Analyze overlap condition

    Using '<=' excludes intervals that touch at a point (e.g., end == start), missing valid intersections.
  2. Step 2: Correct condition

    Changing to '<' ensures intervals that share a boundary point are considered intersecting.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Inclusive endpoints require '<' not '<=' to detect touching intervals [OK]
Hint: Check boundary conditions carefully for inclusive intervals [OK]
Common Mistakes:
  • Using <= instead of <
  • Reversing pointer increments
  • Ignoring empty inputs
4. The following code attempts to merge intervals in-place after sorting. Identify the line that contains a subtle bug causing incorrect results on some inputs.
medium
A. Line 3: intervals.sort(key=lambda x: x[0])
B. Line 9: intervals[index][1] = max(intervals[index][1], intervals[i][1])
C. Line 12: return intervals # missing slicing after in-place merge
D. Line 8: if intervals[i][0] <= intervals[index][1]:

Solution

  1. Step 1: Understand the in-place merge modifies intervals up to index.

    After merging, only intervals[:index+1] are valid merged intervals.
  2. Step 2: Identify the bug in the return statement.

    Returning the entire intervals list without slicing includes extra unmerged intervals, causing incorrect output.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Return intervals[:index+1] to exclude leftover intervals. [OK]
Hint: Return sliced intervals after in-place merge [OK]
Common Mistakes:
  • Forgetting to slice after in-place merge
  • Modifying list while iterating without adjusting index
5. Suppose the problem changes: intervals can be reused infinitely many times, and you want to count how many intervals contain each point considering unlimited reuse (e.g., intervals repeat periodically). Which modification to the line sweep approach correctly handles this scenario?
hard
A. No change needed; line sweep already counts intervals correctly regardless of reuse.
B. Preprocess intervals to merge overlapping intervals into one, then run line sweep once.
C. Use a segment tree or binary indexed tree to handle repeated intervals efficiently instead of line sweep.
D. Modify events to include multiple copies of intervals explicitly and run line sweep on expanded events.

Solution

  1. Step 1: Understand reuse impact

    Infinite reuse means intervals repeat periodically, so naive line sweep with explicit events cannot handle infinite copies.
  2. Step 2: Recognize data structure need

    Segment trees or binary indexed trees can efficiently query counts over ranges and handle repeated intervals without enumerating all copies.
  3. Step 3: Why other options fail

    No change (A) ignores infinite reuse; merging (B) loses count detail; explicit expansion (D) is infeasible for infinite repeats.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Segment trees handle range queries with repeated intervals efficiently [OK]
Hint: Infinite reuse requires data structures, not event enumeration [OK]
Common Mistakes:
  • Assuming line sweep handles infinite repeats
  • Trying to expand events explicitly
  • Merging intervals loses count accuracy
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard