Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogleMicrosoft

Minimum Number of Platforms Required

Choose your preparation mode4 modes available
</>
IDE
def min_platforms_brute_force(arrivals: list[int], departures: list[int]) -> int:public int minPlatforms(int[] arrivals, int[] departures)int minPlatforms(vector<int> arrivals, vector<int> departures)function minPlatforms(arrivals, departures)
def min_platforms_brute_force(arrivals, departures):
    # Write your solution here
    pass
class Solution {
    public int minPlatforms(int[] arrivals, int[] departures) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int minPlatforms(vector<int> arrivals, vector<int> departures) {
    // Write your solution here
    return 0;
}
function minPlatforms(arrivals, departures) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: 1Counting only one platform regardless of overlaps due to missing sorting or overlap logic.✅ Sort arrivals and departures separately and use two pointers to count maximum simultaneous trains.
Wrong: 0Returning 0 for non-empty input due to missing base case for single train or empty input handling.✅ Add base case: if n == 0 return 0; if n == 1 return 1.
Wrong: 2Off-by-one error when arrival equals departure causing undercount of platforms.✅ When arrival == departure, increment departure pointer first to free platform before counting new arrival.
Wrong: TLEUsing nested loops O(n^2) brute force approach for large inputs.✅ Implement sorting and two-pointer sweep line approach with O(n log n) complexity.
✓
Test Cases
t1_01basic
Input{"arrivals":[900,940,950,1100,1500,1800],"departures":[910,1200,1120,1130,1900,2000]}
Expected3

At time 950, trains 1, 2, and 3 are at the station simultaneously, requiring 3 platforms.

t1_02basic
Input{"arrivals":[100,200,300,400],"departures":[150,250,350,450]}
Expected1

Each train departs before the next arrives, so only one platform is needed.

t2_01edge
Input{"arrivals":[],"departures":[]}
Expected0

No trains means no platforms needed.

t2_02edge
Input{"arrivals":[500],"departures":[600]}
Expected1

Only one train requires one platform.

t2_03edge
Input{"arrivals":[1000,1000,1000],"departures":[1000,1000,1000]}
Expected3

All trains arrive and depart at the same time, so each needs a separate platform.

t2_04edge
Input{"arrivals":[100,200,300],"departures":[200,300,400]}
Expected1

Trains arrive exactly when previous train departs, so two platforms are needed due to overlap at boundary.

t3_01corner
Input{"arrivals":[900,940,950,1100],"departures":[910,1200,1120,1130]}
Expected3

Greedy approach picking earliest departure first fails; correct max overlap is 3.

t3_02corner
Input{"arrivals":[100,200,300,400,500],"departures":[300,400,500,600,700]}
Expected2

Overlapping intervals require counting all overlaps; arrival equal to departure counts as overlap.

t3_03corner
Input{"arrivals":[900,940,950,1100,1500],"departures":[910,1200,1120,1130,1900]}
Expected3

Off-by-one error in pointer increments causes wrong platform count; correct max overlap is 2.

t4_01performance
Input{"arrivals":[0,10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990],"departures":[5,15,25,35,45,55,65,75,85,95,105,115,125,135,145,155,165,175,185,195,205,215,225,235,245,255,265,275,285,295,305,315,325,335,345,355,365,375,385,395,405,415,425,435,445,455,465,475,485,495,505,515,525,535,545,555,565,575,585,595,605,615,625,635,645,655,665,675,685,695,705,715,725,735,745,755,765,775,785,795,805,815,825,835,845,855,865,875,885,895,905,915,925,935,945,955,965,975,985,995]}
⏱ Performance - must finish in 2000ms

n=100, O(n log n) sorting and O(n) two-pointer sweep line must complete within 2 seconds.

Practice

(1/5)
1. Consider the following code snippet implementing the sweep line approach for Employee Free Time. Given the input schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]], what is the final returned list of free time intervals?
easy
A. [[3,4],[6,10]]
B. [[3,4]]
C. [[3,4],[6,7]]
D. [[3,4],[6,10]]

Solution

  1. Step 1: Sort events and track active intervals

    Events: (1,1),(1,1),(2,-1),(3,-1),(4,1),(5,1),(6,-1),(10,-1). Active counts track busy employees.
  2. Step 2: Identify free intervals when active==0 between events

    Free time occurs between 3 and 4 only, as after 4 active increments again until 10.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Only [3,4] is free time interval [OK]
Hint: Free time only when no active intervals between events [OK]
Common Mistakes:
  • Including intervals after 6 incorrectly as free time
2. You are given a list of non-overlapping intervals sorted by their start times, and a new interval to insert. Which approach guarantees an optimal solution that correctly merges overlapping intervals after insertion?
easy
A. Use a greedy approach that inserts the new interval at the end and merges overlapping intervals in one pass without sorting.
B. Iterate through intervals and insert the new interval in the correct position without sorting, then merge overlapping intervals.
C. Use dynamic programming to find the minimal set of merged intervals after insertion.
D. Append the new interval, sort all intervals by start time, then merge overlapping intervals in one pass.

Solution

  1. Step 1: Understand the problem constraints

    The intervals are sorted and non-overlapping initially, but inserting a new interval may cause overlaps.
  2. Step 2: Identify the approach that guarantees correct merging

    Appending and then sorting ensures the new interval is placed correctly relative to others, allowing a single pass merge to handle all overlaps reliably.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Sorting after insertion ensures correct order for merging [OK]
Hint: Sort after insertion to guarantee correct merge order [OK]
Common Mistakes:
  • Assuming intervals remain sorted after insertion without sorting
  • Trying to merge without sorting leads to missed overlaps
  • Using DP unnecessarily complicates the problem
3. What is the time complexity of the optimal algorithm that determines if a person can attend all meetings given n intervals, where the algorithm sorts intervals by start time and then checks for overlaps in a single pass?
medium
A. O(n) because we only scan the intervals once after sorting
B. O(n^2) because each interval is compared with all others for overlaps
C. O(n log n) due to sorting the intervals by start time
D. O(log n) because sorting can be done in logarithmic time

Solution

  1. Step 1: Identify sorting cost

    Sorting n intervals by start time takes O(n log n) time.
  2. Step 2: Identify overlap check cost

    Single pass to check overlaps is O(n), which is dominated by sorting.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting dominates total time complexity [OK]
Hint: Sorting dominates complexity -> O(n log n) [OK]
Common Mistakes:
  • Confusing single pass check as O(n log n)
  • Assuming nested loops cause O(n^2) here
4. 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
5. Suppose balloons can be reused multiple times after bursting (i.e., an arrow can burst a balloon multiple times if shot at different points). How does this affect the algorithm to find the minimum number of arrows needed?
hard
A. The original greedy algorithm still applies without changes.
B. We must use dynamic programming to track multiple bursts per balloon.
C. The problem reduces to counting unique balloons since reuse removes overlap constraints.
D. We can shoot arrows only at balloon start points to minimize arrows.

Solution

  1. Step 1: Understand reuse effect

    If balloons can be burst multiple times independently, overlapping intervals no longer reduce arrow count.
  2. Step 2: Simplify problem

    Each balloon requires at least one arrow, so minimum arrows equal number of unique balloons.
  3. Step 3: Algorithm implication

    Overlap and interval sorting become irrelevant; counting balloons suffices.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Reuse breaks overlap optimization, so count balloons directly [OK]
Hint: Reuse removes overlap benefit; count balloons directly [OK]
Common Mistakes:
  • Assuming greedy still works unchanged
  • Trying to track multiple bursts with DP unnecessarily
  • Ignoring that reuse breaks interval overlap logic
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