Minimum Number of Platforms Required

🎯

Minimum Number of Platforms Required

mediumINTERVALSAmazonGoogleMicrosoft

Imagine a busy train station where multiple trains arrive and depart at different times. You need to figure out the minimum number of platforms so that no train has to wait.

💡 This problem involves managing overlapping intervals, which can be tricky for beginners because it requires understanding how intervals interact over time and how to efficiently track these overlaps. Think of it like scheduling rooms for meetings where you need to know how many rooms are occupied at the same time.

📋

Problem Statement

Given arrival and departure times of trains on a single day, find the minimum number of platforms required so that no train waits for another to leave. Input: Two arrays of equal length n, arrivals and departures, where arrivals[i] and departures[i] represent the arrival and departure times of the ith train. Output: An integer representing the minimum number of platforms needed.

1 ≤ n ≤ 10^50 ≤ arrivals[i] < departures[i] ≤ 10^9All times are in the same day and in the same unit (e.g., minutes from midnight)

💡

Example

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

Output3

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

• All trains arrive and depart at the same time → platforms = n
• Trains arrive after all previous trains have departed → platforms = 1
• Only one train → platforms = 1
• Trains with arrival time equal to departure time of another train → platforms = 1

⚠️

Common Mistakes

Not sorting arrivals and departures separately

Incorrect platform count due to unordered event processing

✅ Sort both arrays independently before processing

Treating arrival and departure at the same time incorrectly

Overcounting platforms when a train departs and another arrives simultaneously

✅ When sorting events, process departures before arrivals if times are equal

Using nested loops for large inputs

Time limit exceeded (TLE) due to O(n^2) complexity

✅ Use sorting and two-pointer or sweep line approach for O(n log n) solutions

Not updating max_platforms after each event

Final answer underestimates the required platforms

✅ Update max_platforms whenever platforms_needed changes

Modifying input arrays without copying

Unexpected side effects if inputs are reused elsewhere

✅ Copy arrays before sorting or document that inputs are modified

🧠

Brute Force (Nested Loops Checking Overlaps)

💡 This approach exists to build intuition by directly checking overlaps between every pair of trains, helping beginners understand the core problem of interval overlaps before optimizing. It is like checking every pair of meetings to see if they clash.

Intuition

For each train, count how many other trains overlap with it by comparing arrival and departure times. The maximum overlap count is the minimum number of platforms needed.

Algorithm

1. Initialize max_platforms to 1.
2. For each train i, count how many trains j overlap with i by checking if arrivals[j] < departures[i] and departures[j] > arrivals[i].
3. Update max_platforms with the maximum overlap count found.
4. Return max_platforms.

💡 The nested loops make it easy to see how overlaps are counted but can be inefficient for large inputs.

</>

Code

def min_platforms_brute_force(arrivals, departures):
    n = len(arrivals)
    max_platforms = 1
    for i in range(n):
        count = 1
        for j in range(n):
            if i != j and arrivals[j] < departures[i] and departures[j] > arrivals[i]:
                count += 1
        max_platforms = max(max_platforms, count)
    return max_platforms

# Driver code
if __name__ == '__main__':
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1200, 1120, 1130, 1900, 2000]
    print(min_platforms_brute_force(arrivals, departures))  # Output: 3

Line Notes

n = len(arrivals)Determine the number of trains to iterate over all pairs.

for i in range(n)Outer loop selects the current train to check overlaps against.

for j in range(n)Inner loop compares current train with every other train.

if i != j and arrivals[j] < departures[i] and departures[j] > arrivals[i]Check if train j overlaps with train i by ensuring their intervals intersect.

max_platforms = max(max_platforms, count)Update the maximum number of overlapping trains found so far.

public class MinPlatformsBruteForce {
    public static int minPlatforms(int[] arrivals, int[] departures) {
        int n = arrivals.length;
        int maxPlatforms = 1;
        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n; j++) {
                if (i != j && arrivals[j] < departures[i] && departures[j] > arrivals[i]) {
                    count++;
                }
            }
            maxPlatforms = Math.max(maxPlatforms, count);
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(minPlatforms(arrivals, departures)); // Output: 3
    }
}

Line Notes

int n = arrivals.length;Get the number of trains for iteration.

for (int i = 0; i < n; i++) {Outer loop picks each train to check overlaps.

for (int j = 0; j < n; j++) {Inner loop compares with every other train.

if (i != j && arrivals[j] < departures[i] && departures[j] > arrivals[i]) {Check if train j overlaps with train i.

maxPlatforms = Math.max(maxPlatforms, count);Keep track of the maximum overlap count.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minPlatformsBruteForce(const vector<int>& arrivals, const vector<int>& departures) {
    int n = arrivals.size();
    int maxPlatforms = 1;
    for (int i = 0; i < n; i++) {
        int count = 1;
        for (int j = 0; j < n; j++) {
            if (i != j && arrivals[j] < departures[i] && departures[j] > arrivals[i]) {
                count++;
            }
        }
        maxPlatforms = max(maxPlatforms, count);
    }
    return maxPlatforms;
}

int main() {
    vector<int> arrivals = {900, 940, 950, 1100, 1500, 1800};
    vector<int> departures = {910, 1200, 1120, 1130, 1900, 2000};
    cout << minPlatformsBruteForce(arrivals, departures) << endl; // Output: 3
    return 0;
}

Line Notes

int n = arrivals.size();Determine number of trains for nested iteration.

for (int i = 0; i < n; i++) {Outer loop selects train i to check overlaps.

for (int j = 0; j < n; j++) {Inner loop compares train i with train j.

if (i != j && arrivals[j] < departures[i] && departures[j] > arrivals[i]) {Check if intervals overlap between trains i and j.

maxPlatforms = max(maxPlatforms, count);Update maximum platforms needed so far.

function minPlatformsBruteForce(arrivals, departures) {
    const n = arrivals.length;
    let maxPlatforms = 1;
    for (let i = 0; i < n; i++) {
        let count = 1;
        for (let j = 0; j < n; j++) {
            if (i !== j && arrivals[j] < departures[i] && departures[j] > arrivals[i]) {
                count++;
            }
        }
        maxPlatforms = Math.max(maxPlatforms, count);
    }
    return maxPlatforms;
}

// Test
const arrivals = [900, 940, 950, 1100, 1500, 1800];
const departures = [910, 1200, 1120, 1130, 1900, 2000];
console.log(minPlatformsBruteForce(arrivals, departures)); // Output: 3

Line Notes

const n = arrivals.length;Get total number of trains for iteration.

for (let i = 0; i < n; i++) {Outer loop picks train i to check overlaps.

for (let j = 0; j < n; j++) {Inner loop compares train i with train j.

if (i !== j && arrivals[j] < departures[i] && departures[j] > arrivals[i]) {Check if train j overlaps with train i.

maxPlatforms = Math.max(maxPlatforms, count);Update maximum number of platforms needed.

⏱

Complexity

TimeO(n^2)

SpaceO(1)

We check every pair of trains for overlap, resulting in n*n comparisons.

💡 For n=20, this means 400 comparisons, which is manageable, but for n=100000, it becomes 10 billion, which is too slow.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but is useful to understand the problem and overlaps before optimizing.

🧠

Sorting Arrivals and Departures with Two Pointers

💡 This approach improves efficiency by sorting arrival and departure times separately and using two pointers to simulate the timeline, which is a common technique in interval problems. It helps you think of the problem as a timeline of events.

Intuition

Sort arrivals and departures. Use two pointers to traverse both arrays. Increment platform count when a train arrives before the earliest departure, decrement when a train departs before the next arrival.

Algorithm

1. Sort the arrivals and departures arrays.
2. Initialize two pointers i and j to 0, and variables platforms_needed and max_platforms to 0.
3. While i < n and j < n, if arrivals[i] <= departures[j], increment platforms_needed and i; else decrement platforms_needed and increment j.
4. Update max_platforms with the maximum platforms_needed during traversal.
5. Return max_platforms.

💡 Sorting allows us to process events in chronological order, and two pointers help track how many trains are at the station simultaneously.

</>

Code

def min_platforms_two_pointers(arrivals, departures):
    arrivals.sort()
    departures.sort()
    n = len(arrivals)
    i = j = 0
    platforms_needed = max_platforms = 0
    while i < n and j < n:
        if arrivals[i] <= departures[j]:
            platforms_needed += 1
            max_platforms = max(max_platforms, platforms_needed)
            i += 1
        else:
            platforms_needed -= 1
            j += 1
    return max_platforms

# Driver code
if __name__ == '__main__':
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1200, 1120, 1130, 1900, 2000]
    print(min_platforms_two_pointers(arrivals, departures))  # Output: 3

Line Notes

arrivals.sort()Sort arrival times to process in chronological order.

departures.sort()Sort departure times similarly for comparison.

n = len(arrivals)Get the total number of trains.

i = j = 0Initialize pointers for arrivals and departures.

platforms_needed = max_platforms = 0Initialize counters for current and max platforms needed.

while i < n and j < n:Traverse both arrays simultaneously to simulate timeline.

if arrivals[i] <= departures[j]:If next event is arrival, need a platform.

platforms_needed += 1Increment platform count for arriving train.

max_platforms = max(max_platforms, platforms_needed)Track maximum platforms needed so far.

else:If next event is departure, free a platform.

platforms_needed -= 1Decrement platform count for departing train.

import java.util.Arrays;

public class MinPlatformsTwoPointers {
    public static int minPlatforms(int[] arrivals, int[] departures) {
        Arrays.sort(arrivals);
        Arrays.sort(departures);
        int n = arrivals.length;
        int i = 0, j = 0;
        int platformsNeeded = 0, maxPlatforms = 0;
        while (i < n && j < n) {
            if (arrivals[i] <= departures[j]) {
                platformsNeeded++;
                maxPlatforms = Math.max(maxPlatforms, platformsNeeded);
                i++;
            } else {
                platformsNeeded--;
                j++;
            }
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(minPlatforms(arrivals, departures)); // Output: 3
    }
}

Line Notes

Arrays.sort(arrivals);Sort arrivals to process in order.

Arrays.sort(departures);Sort departures similarly.

int n = arrivals.length;Get total number of trains.

int i = 0, j = 0;Initialize pointers for arrivals and departures.

int platformsNeeded = 0, maxPlatforms = 0;Initialize counters for current and max platforms needed.

while (i < n && j < n) {Traverse both arrays to simulate timeline.

if (arrivals[i] <= departures[j]) {Arrival event requires platform increment.

platformsNeeded++;Increase platform count for arriving train.

maxPlatforms = Math.max(maxPlatforms, platformsNeeded);Track max platforms needed.

else {Departure event frees a platform.

platformsNeeded--;Decrease platform count for departing train.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minPlatformsTwoPointers(vector<int>& arrivals, vector<int>& departures) {
    sort(arrivals.begin(), arrivals.end());
    sort(departures.begin(), departures.end());
    int n = arrivals.size();
    int i = 0, j = 0;
    int platformsNeeded = 0, maxPlatforms = 0;
    while (i < n && j < n) {
        if (arrivals[i] <= departures[j]) {
            platformsNeeded++;
            maxPlatforms = max(maxPlatforms, platformsNeeded);
            i++;
        } else {
            platformsNeeded--;
            j++;
        }
    }
    return maxPlatforms;
}

int main() {
    vector<int> arrivals = {900, 940, 950, 1100, 1500, 1800};
    vector<int> departures = {910, 1200, 1120, 1130, 1900, 2000};
    cout << minPlatformsTwoPointers(arrivals, departures) << endl; // Output: 3
    return 0;
}

Line Notes

sort(arrivals.begin(), arrivals.end());Sort arrivals for chronological processing.

sort(departures.begin(), departures.end());Sort departures similarly.

int n = arrivals.size();Get total number of trains.

int i = 0, j = 0;Initialize pointers for arrivals and departures.

int platformsNeeded = 0, maxPlatforms = 0;Initialize counters for current and max platforms needed.

while (i < n && j < n) {Traverse both arrays simulating timeline.

if (arrivals[i] <= departures[j]) {Arrival event means platform needed.

platformsNeeded++;Increment platform count.

maxPlatforms = max(maxPlatforms, platformsNeeded);Track max platforms needed.

else {Departure event frees platform.

platformsNeeded--;Decrement platform count.

function minPlatformsTwoPointers(arrivals, departures) {
    arrivals.sort((a, b) => a - b);
    departures.sort((a, b) => a - b);
    const n = arrivals.length;
    let i = 0, j = 0;
    let platformsNeeded = 0, maxPlatforms = 0;
    while (i < n && j < n) {
        if (arrivals[i] <= departures[j]) {
            platformsNeeded++;
            maxPlatforms = Math.max(maxPlatforms, platformsNeeded);
            i++;
        } else {
            platformsNeeded--;
            j++;
        }
    }
    return maxPlatforms;
}

// Test
const arrivals = [900, 940, 950, 1100, 1500, 1800];
const departures = [910, 1200, 1120, 1130, 1900, 2000];
console.log(minPlatformsTwoPointers(arrivals, departures)); // Output: 3

Line Notes

arrivals.sort((a, b) => a - b);Sort arrivals for chronological order.

departures.sort((a, b) => a - b);Sort departures similarly.

const n = arrivals.length;Get total number of trains.

let i = 0, j = 0;Initialize pointers for arrivals and departures.

let platformsNeeded = 0, maxPlatforms = 0;Initialize counters for current and max platforms needed.

while (i < n && j < n) {Traverse both arrays simulating timeline.

if (arrivals[i] <= departures[j]) {Arrival event requires platform increment.

platformsNeeded++;Increase platform count for arriving train.

maxPlatforms = Math.max(maxPlatforms, platformsNeeded);Track max platforms needed.

else {Departure event frees a platform.

platformsNeeded--;Decrease platform count.

⏱

Complexity

TimeO(n log n)

SpaceO(1)

Sorting takes O(n log n), and the two-pointer traversal is O(n).

💡 For n=100000, sorting is feasible and traversal is linear, making this approach efficient.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews for this problem.

🧠

Sweep Line Algorithm Using Events

💡 This approach models arrivals and departures as events on a timeline, processing them in order to track platform usage dynamically, which is a powerful technique for interval problems. It generalizes the two-pointer method by treating all events uniformly.

Intuition

Create a combined list of arrival and departure events, sort by time, and sweep through them. Increment platform count on arrival, decrement on departure, tracking the maximum simultaneously needed.

Algorithm

1. Create an events list with tuples (time, type), where type is +1 for arrival and -1 for departure.
2. Sort the events by time; if times are equal, departures (-1) come before arrivals (+1) to free platforms first.
3. Initialize platforms_needed and max_platforms to 0.
4. Traverse the events, adding type to platforms_needed at each event.
5. Update max_platforms with the maximum platforms_needed during traversal.
6. Return max_platforms.

💡 Sorting events and processing them in order simulates the timeline precisely, handling simultaneous arrivals and departures correctly.

</>

Code

def min_platforms_sweep_line(arrivals, departures):
    events = []
    for time in arrivals:
        events.append((time, 1))  # arrival
    for time in departures:
        events.append((time, -1))  # departure
    # Sort by time; if tie, departure (-1) before arrival (1)
    events.sort(key=lambda x: (x[0], x[1]))
    platforms_needed = max_platforms = 0
    for _, event_type in events:
        platforms_needed += event_type
        max_platforms = max(max_platforms, platforms_needed)
    return max_platforms

# Driver code
if __name__ == '__main__':
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1200, 1120, 1130, 1900, 2000]
    print(min_platforms_sweep_line(arrivals, departures))  # Output: 3

Line Notes

events = []Initialize list to hold all arrival and departure events.

for time in arrivals:Add all arrival events with +1 indicating platform needed.

for time in departures:Add all departure events with -1 indicating platform freed.

events.sort(key=lambda x: (x[0], x[1]))Sort events by time; departures before arrivals if times are equal to free platforms first.

platforms_needed += event_typeUpdate platform count based on event type.

max_platforms = max(max_platforms, platforms_needed)Track maximum platforms needed.

import java.util.*;

public class MinPlatformsSweepLine {
    public static int minPlatforms(int[] arrivals, int[] departures) {
        List<int[]> events = new ArrayList<>();
        for (int time : arrivals) {
            events.add(new int[]{time, 1}); // arrival
        }
        for (int time : departures) {
            events.add(new int[]{time, -1}); // departure
        }
        events.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1]; // departure (-1) before arrival (1)
        });
        int platformsNeeded = 0, maxPlatforms = 0;
        for (int[] event : events) {
            platformsNeeded += event[1];
            maxPlatforms = Math.max(maxPlatforms, platformsNeeded);
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(minPlatforms(arrivals, departures)); // Output: 3
    }
}

Line Notes

List<int[]> events = new ArrayList<>();Create list to hold all events with time and type.

events.add(new int[]{time, 1});Add arrival events with +1 to indicate platform needed.

events.add(new int[]{time, -1});Add departure events with -1 to indicate platform freed.

events.sort((a, b) -> { ... });Sort events by time, departures before arrivals if tie to free platforms first.

platformsNeeded += event[1];Update platform count based on event type.

maxPlatforms = Math.max(maxPlatforms, platformsNeeded);Track maximum platforms needed.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minPlatformsSweepLine(const vector<int>& arrivals, const vector<int>& departures) {
    vector<pair<int, int>> events;
    for (int time : arrivals) {
        events.emplace_back(time, 1); // arrival
    }
    for (int time : departures) {
        events.emplace_back(time, -1); // departure
    }
    sort(events.begin(), events.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second; // departure (-1) before arrival (1)
    });
    int platformsNeeded = 0, maxPlatforms = 0;
    for (auto& event : events) {
        platformsNeeded += event.second;
        maxPlatforms = max(maxPlatforms, platformsNeeded);
    }
    return maxPlatforms;
}

int main() {
    vector<int> arrivals = {900, 940, 950, 1100, 1500, 1800};
    vector<int> departures = {910, 1200, 1120, 1130, 1900, 2000};
    cout << minPlatformsSweepLine(arrivals, departures) << endl; // Output: 3
    return 0;
}

Line Notes

vector<pair<int, int>> events;Create vector to hold all events with time and type.

events.emplace_back(time, 1);Add arrival events with +1 indicating platform needed.

events.emplace_back(time, -1);Add departure events with -1 indicating platform freed.

sort(events.begin(), events.end(), ...);Sort events by time; departures before arrivals if tie.

platformsNeeded += event.second;Update platform count based on event type.

maxPlatforms = max(maxPlatforms, platformsNeeded);Track maximum platforms needed.

function minPlatformsSweepLine(arrivals, departures) {
    const events = [];
    for (const time of arrivals) {
        events.push([time, 1]); // arrival
    }
    for (const time of departures) {
        events.push([time, -1]); // departure
    }
    events.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1]; // departure (-1) before arrival (1)
    });
    let platformsNeeded = 0, maxPlatforms = 0;
    for (const [, type] of events) {
        platformsNeeded += type;
        maxPlatforms = Math.max(maxPlatforms, platformsNeeded);
    }
    return maxPlatforms;
}

// Test
const arrivals = [900, 940, 950, 1100, 1500, 1800];
const departures = [910, 1200, 1120, 1130, 1900, 2000];
console.log(minPlatformsSweepLine(arrivals, departures)); // Output: 3

Line Notes

const events = [];Initialize array to hold all events with time and type.

events.push([time, 1]);Add arrival events with +1 indicating platform needed.

events.push([time, -1]);Add departure events with -1 indicating platform freed.

events.sort((a, b) => { ... });Sort events by time; departures before arrivals if tie.

platformsNeeded += type;Update platform count based on event type.

maxPlatforms = Math.max(maxPlatforms, platformsNeeded);Track maximum platforms needed.

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting events takes O(n log n), and processing them is O(n).

💡 This approach uses extra space for events but is efficient and clear for handling simultaneous events.

Interview Verdict: Accepted

This is an optimal and elegant approach, especially useful when event attributes grow more complex.

📊

All Approaches - One-Glance Tradeoffs

💡 The two-pointer and sweep line approaches are the best to code in interviews due to their efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Sorting + Two Pointers	O(n log n)	O(1)	No	N/A	Code this for efficient solution
3. Sweep Line Algorithm	O(n log n)	O(n)	No	N/A	Code this for clarity and event-based problems

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Start with the brute force approach to demonstrate understanding of overlaps.Explain the inefficiency and move to sorting arrivals and departures with two pointers.Discuss the sweep line approach as a generalization and its advantages.Write clean, tested code for the chosen approach.Test edge cases and discuss time/space complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of interval overlaps, ability to optimize from brute force to efficient solutions, and clarity in explaining your approach.

Common Follow-ups

• What if arrival and departure times can be the same? → Handle by sorting departures before arrivals.
• How to handle multiple stations or platforms with different constraints? → Extend event processing or use segment trees.
• Can you output the actual platform assignments? → Use a priority queue to assign platforms.
• What if trains can arrive and depart multiple times? → Model as multiple intervals and apply the same logic.

💡 These follow-ups test your ability to adapt the solution to variations and demonstrate deeper understanding.

🔍

Pattern Recognition

When to Use

1) Problem involves intervals or time ranges; 2) Need to find maximum overlap or concurrency; 3) Events have start and end times; 4) Asked for minimum resources to handle all intervals.

Signature Phrases

minimum number of platformsarrival and departure timesno train waits

NOT This Pattern When

Problems that only ask for interval merging or counting intervals without overlap considerations.

Similar Problems

Meeting Rooms II - also finds minimum rooms for overlapping meetingsCar Pooling - tracks capacity over intervalsEmployee Free Time - finds gaps in intervals

Practice

1. Given multiple employees' schedules with intervals representing their busy times, which algorithmic approach guarantees finding all common free time intervals where no employee is busy?

easy

A. Greedy interval scheduling that picks earliest finishing intervals

B. Dynamic programming to find maximum non-overlapping intervals

C. Sweep line / event processing that tracks interval start and end events

D. Brute force checking every time point across all intervals

Solution

1. Step 1: Understand problem requires identifying gaps where no intervals overlap

   Greedy scheduling or DP focus on selecting intervals, not gaps between them.

2. Step 2: Sweep line processes all start/end events in order, tracking active intervals to find free gaps

   This approach efficiently detects when no employee is busy, yielding correct free times.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sweep line tracks active intervals and finds free gaps [OK]

Hint: Sweep line tracks interval endpoints to find free gaps [OK]

Common Mistakes:

• Assuming greedy or DP can find free gaps directly

2. 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

3. What is the time complexity of the optimal approach that inserts a new interval into a list of n intervals and merges overlapping intervals, where the approach is to append the new interval, sort all intervals by start time, then merge in one pass?

medium

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)

Solution

1. Step 1: Identify sorting cost

   Appending is O(1), but sorting n+1 intervals takes O(n log n) time.

2. Step 2: Identify merging cost

   Merging intervals in one pass is O(n) since each interval is processed once.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates overall time complexity [OK]

Hint: Sorting dominates time complexity -> O(n log n) [OK]

Common Mistakes:

• Assuming linear time because merging is O(n)
• Confusing sorting cost with merging cost
• Thinking recursion stack adds extra complexity

4. What is the time complexity of the optimal two pointers approach for finding the intersection of two interval lists, each of length m and n respectively?

medium

A. O(max(m, n) * log(min(m, n))) due to sorting or binary search steps.

B. O(m * n), since each interval in one list is compared to all intervals in the other list.

C. O(m + n), because each pointer advances at most m or n times through the lists.

D. O(m + n + k), where k is the number of intersections found.

Solution

1. Step 1: Identify pointer movements

   Each pointer i and j moves forward only, never backward, up to m and n times respectively.

2. Step 2: Sum pointer advances

   Total steps ≤ m + n, so time complexity is O(m + n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two pointers scan each list once without nested loops [OK]

Hint: Two pointers each advance linearly, no nested iteration [OK]

Common Mistakes:

• Confusing with brute force O(m*n)
• Assuming sorting is needed
• Including output size k in complexity incorrectly

5. Suppose the problem is modified so that intervals can be reused multiple times for different queries, and queries can be negative integers. Which modification to the binary search + preprocessing approach is necessary to handle this variant correctly and efficiently?

hard

A. Preprocess intervals by length and use a segment tree to query coverage efficiently for negative and repeated queries.

B. No change needed; the original approach works for reuse and negative queries.

C. Sort queries and intervals, use a min-heap to maintain active intervals covering queries in order.

D. Use brute force checking each interval for each query since reuse breaks binary search assumptions.

Solution

1. Step 1: Identify challenges with reuse and negative queries

   Negative queries require data structures supporting arbitrary ranges; reuse means intervals must be efficiently queried multiple times.

2. Step 2: Choose appropriate data structure

   Segment tree or interval tree allows efficient coverage queries over any integer range and supports multiple queries efficiently.

3. Step 3: Why other options fail

   Min-heap approach requires sorting queries and intervals but doesn't handle negative queries well; brute force is inefficient; original approach assumes positive queries and no reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Segment tree supports arbitrary queries and reuse efficiently [OK]

Hint: Segment tree handles arbitrary queries and reuse [OK]

Common Mistakes:

• Assuming original approach works unchanged
• Using min-heap without sorting queries
• Resorting to brute force unnecessarily