Minimum Number of Platforms Required

📋

Minimum Number of Platforms Required

Edge cases:

</>

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
}

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

Try testing your solution on empty and single train inputs to catch base case bugs.

Consider tricky overlaps and equal arrival/departure times to catch algorithmic mistakes.

Optimize your solution to O(n log n) by sorting and using a two-pointer sweep line approach.

t1_01basic

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Sort arrival and departure times to process events chronologically.

💡 Use two pointers to track arrivals and departures and count overlapping trains.

💡 Increment platform count on arrival before departure pointer moves; decrement on departure.

Why it failed: Incorrect platform count due to not properly counting simultaneous trains. Fix by sorting arrivals and departures separately and using two pointers to track overlaps.

✓ Correctly counts maximum overlapping trains using sorted arrivals and departures.

t1_02basic

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

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Check if any trains overlap by comparing arrival of next train with departure of current.

💡 If arrivals[i] >= departures[i-1], no overlap; platforms needed remain 1.

💡 Ensure to update platform count only when trains overlap.

Why it failed: Overcounting platforms by not checking if next train arrives after previous departs. Fix by comparing arrivals[i] with departures[j] and incrementing platforms only on overlap.

✓ Correctly identifies no overlaps, resulting in one platform needed.

t2_01edge

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

Expected0

⏱ Performance - must finish in 2000ms

No trains means no platforms needed.

💡 Consider the case when input arrays are empty.

💡 Return 0 immediately if no trains are present.

💡 Avoid processing when n=0 to prevent errors.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a base case: if n == 0, return 0.

✓ Handles empty input gracefully, returning 0 platforms.

t2_02edge

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

Expected1

⏱ Performance - must finish in 2000ms

Only one train requires one platform.

💡 Check behavior with a single train input.

💡 Minimum platforms needed is always 1 if there is at least one train.

💡 Ensure no off-by-one errors in loops for single element.

Why it failed: Returns 0 or more than 1 for single train. Fix by returning 1 when n=1.

✓ Correctly returns 1 platform for single train.

t2_03edge

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Consider trains with identical arrival and departure times.

💡 Each train occupies a platform simultaneously if times are equal.

💡 Count all trains when arrivals equal departures to get platforms needed.

Why it failed: Fails to count all trains when arrival equals departure time. Fix by treating arrival == departure as overlap requiring separate platforms.

✓ Correctly counts all trains needing separate platforms when times coincide.

t2_04edge

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

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Check if arrival time equal to departure time counts as overlap.

💡 If arrival == departure, platform cannot be reused immediately; count as overlap.

💡 Increment platform count when arrival <= departure to handle boundary overlaps.

Why it failed: Incorrectly counts arrival == departure as non-overlap causing undercount of platforms. Fix by counting arrival == departure as overlap and incrementing platform count accordingly.

✓ Correctly counts platforms needed when arrival equals departure time.

t3_01corner

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Beware of greedy approach that picks earliest departure without considering all overlaps.

💡 Use sweep line or two-pointer technique to count simultaneous trains.

💡 Sort arrivals and departures separately and count overlaps correctly.

Why it failed: Greedy approach undercounts platforms by not considering all overlapping intervals. Fix by sorting arrivals and departures separately and using two pointers to track overlaps.

✓ Correctly handles overlapping intervals beyond greedy assumptions.

t3_02corner

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

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Do not treat intervals as non-overlapping if arrival equals previous departure.

💡 Check if arrival <= departure to count overlap, not arrival < departure.

💡 Use inclusive condition to detect overlaps correctly.

Why it failed: Incorrectly treats arrival == departure as non-overlapping, undercounting platforms. Fix by using inclusive inequality arrival <= departure to detect overlaps.

✓ Correctly counts overlaps with inclusive inequality.

t3_03corner

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Check pointer increments carefully when arrivals[i] == departures[j].

💡 Decide whether to increment arrival or departure pointer first to avoid double counting.

💡 When arrival == departure, increment departure pointer first to free platform.

Why it failed: Off-by-one error by incrementing arrival pointer before departure when times equal. Fix by incrementing departure pointer first when arrival == departure.

✓ Correctly handles equal arrival and departure times without overcounting.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Sorting arrivals and departures is O(n log n).

💡 Two-pointer sweep line is O(n).

💡 Avoid nested loops to prevent O(n^2) TLE.

Why it failed: TLE due to using O(n^2) brute force approach. Fix by implementing O(n log n) sorting and two-pointer sweep line algorithm.

✓ Algorithm runs within time limit using efficient sorting and sweep line.

Practice

1. Consider the following Python code implementing the min-heap approach to find the minimum number of meeting rooms. Given the input intervals = [[0,30],[5,10],[15,20]], what is the value of the heap after processing the second interval (i=1)?

easy

A. [10]

B. [30, 10]

C. [30, 20]

D. [5, 10]

Solution

1. Step 1: Trace heap after first interval [0,30].

   Heap contains [30] after pushing end time of first meeting.

2. Step 2: Process second interval [5,10].

   Since 5 < 30 (heap[0]), no pop occurs; push 10. Heap now contains [10, 30] (min-heap property).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap stores end times; after second interval, both 30 and 10 are in heap [OK]

Hint: Heap stores end times; no pop if start < earliest end [OK]

Common Mistakes:

• Popping when start < earliest end
• Confusing heap contents order
• Forgetting to push current interval's end

2. You are given a list of time intervals representing booked meeting rooms. Your task is to combine all overlapping intervals into the minimum number of non-overlapping intervals. Which algorithmic approach guarantees an optimal and efficient solution for this problem?

easy

A. Use a greedy approach that always merges the earliest starting interval with the next one without sorting.

B. Sort intervals by start time and then merge overlapping intervals in a single pass.

C. Use dynamic programming to find the maximum number of non-overlapping intervals and then merge accordingly.

D. Check every pair of intervals with nested loops to merge overlaps until no overlaps remain.

Solution

1. Step 1: Understand the problem requires merging overlapping intervals efficiently.

   Sorting intervals by their start time ensures that overlapping intervals are adjacent, enabling a single pass merge.

2. Step 2: Evaluate each option's approach.

   Use a greedy approach that always merges the earliest starting interval with the next one without sorting. fails because without sorting, intervals may be merged incorrectly or missed. Use dynamic programming to find the maximum number of non-overlapping intervals and then merge accordingly. is unrelated as DP is not needed here. Check every pair of intervals with nested loops to merge overlaps until no overlaps remain. is brute force with O(n²) time, inefficient for large inputs. Sort intervals by start time and then merge overlapping intervals in a single pass. correctly sorts and merges in O(n log n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + one pass merge is the classic optimal pattern for merging intervals. [OK]

Hint: Sort intervals first, then merge in one pass [OK]

Common Mistakes:

• Trying to merge without sorting
• Using nested loops leading to O(n²) time

3. What is the time complexity of the binary search + preprocessing approach for the Minimum Interval to Include Each Query problem, given n intervals and m queries?

medium

A. O(n log n + m n log n)

B. O(n log n + m log n * n)

C. O((n + m) log n)

D. O(n * m)

Solution

1. Step 1: Analyze preprocessing

   Sorting intervals by length takes O(n log n).

2. Step 2: Analyze per query cost

   For each query, binary search over lengths is O(log n), but coverage check scans up to O(n) intervals, so O(n log n) per query.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n log n + m n log n) due to coverage scanning [OK]

Hint: Coverage check inside binary search causes O(n) scan per query [OK]

Common Mistakes:

• Assuming coverage check is O(log n) ignoring linear scan
• Confusing n and m in complexity
• Forgetting sorting cost

4. What is the time complexity of the optimal solution that sorts intervals by start ascending and end descending, then scans once to count uncovered intervals?

medium

A. O(n log n) due to sorting plus O(n) scanning

B. O(n log n) due to sorting, but scanning is O(n²) in worst case

C. O(n) because scanning is linear and sorting is negligible

D. O(n²) due to nested coverage checks

Solution

1. Step 1: Identify sorting cost

   Sorting n intervals by start and end takes O(n log n) time.

2. Step 2: Identify scanning cost

   Single pass scanning to count uncovered intervals is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, scanning is linear [OK]

Hint: Sorting dominates complexity, scanning is linear [OK]

Common Mistakes:

• Confuse scanning as nested loops O(n²)
• Ignore sorting cost and say O(n)

5. Suppose the car pooling problem is modified so that trips can overlap and passengers can be picked up and dropped off multiple times (i.e., trips can reuse the same passengers). Which of the following algorithmic changes correctly adapts the solution to handle this variant efficiently?

hard

A. Use a segment tree or binary indexed tree to efficiently update and query passenger counts over intervals

B. Switch to a priority queue to process events in order and track current passengers dynamically

C. Use the same difference array approach but multiply passenger counts by the number of trips to simulate reuse

D. Modify the difference array to allow negative passenger counts and track net changes carefully

Solution

1. Step 1: Understand reuse complexity

   Reusing passengers means overlapping intervals can increase and decrease counts multiple times, requiring efficient range updates and queries.

2. Step 2: Identify suitable data structure

   Segment trees or binary indexed trees support efficient interval updates and queries, handling overlapping intervals with reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Segment trees handle dynamic interval sums efficiently [OK]

Hint: Reuse -> need data structure for interval updates [OK]

Common Mistakes:

• Multiplying counts breaks logic
• Priority queue alone can't handle reuse efficiently
• Allowing negative counts without structure causes errors