Bird
Raised Fist0
Interview PrepintervalsmediumFacebookAmazonGoogle

Interval List Intersections

Choose your preparation mode4 modes available
📋
Problem

Imagine two friends each have their own schedule of busy time slots, and you want to find all the times when both are busy simultaneously.

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. Each intersection is a closed interval that represents the overlapping time between intervals from the two lists.

1 ≤ number of intervals in each list ≤ 10^5Intervals are sorted by start time and do not overlap within the same listInterval start and end values are integers within a valid range
Edge cases: One or both lists are empty → output is empty listIntervals that touch at a single point (e.g., [1,2] and [2,3]) → intersection is that single point [2,2]One list has intervals completely before or after the other list → no intersections
</>
IDE
def intervalIntersection(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:public List<int[]> intervalIntersection(List<int[]> A, List<int[]> B)vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B)function intervalIntersection(A, B)
def intervalIntersection(A, B):
    # Write your solution here
    pass
class Solution {
    public List<int[]> intervalIntersection(List<int[]> A, List<int[]> B) {
        // Write your solution here
        return new ArrayList<>();
    }
}
#include <vector>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    // Write your solution here
    return {};
}
function intervalIntersection(A, B) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: [[1,5],[8,10],[15,24],[25,25]]Incorrectly adding intervals from one list without intersecting with the other; missing partial overlaps.✅ Compute intersection as [max(startA, startB), min(endA, endB)] only if max start <= min end, and advance pointer of interval with smaller end.
Wrong: [[2,2]]Missing single-point intersections due to strict inequality in overlap check.✅ Use <= in overlap condition: if max(startA, startB) <= min(endA, endB), add intersection.
Wrong: [[1,2],[3,4],[5,6],[1,10]]Treating intervals as unbounded or not advancing pointers properly, causing duplicates or incorrect intervals.✅ Advance pointer of interval with smaller end after processing intersection; do not add intervals without intersection.
Wrong: Timeout or no outputUsing brute force nested loops O(m*n) for large inputs.✅ Implement two-pointer approach with O(m+n) time complexity.
✓
Test Cases
t1_01basic
Input{"A":[[0,2],[5,10],[13,23],[24,25]],"B":[[1,5],[8,12],[15,24],[25,26]]}
Expected[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

We find all overlapping intervals by comparing intervals from A and B and collecting their intersections.

t1_02basic
Input{"A":[[1,3],[5,9]],"B":[[2,5],[7,10]]}
Expected[[2,3],[5,5],[7,9]]

Intersections are [2,3] from [1,3] and [2,5], [5,5] from [5,9] and [2,5], and [7,9] from [5,9] and [7,10].

t2_01edge
Input{"A":[],"B":[[1,3],[5,7]]}
Expected[]

One list is empty, so no intersections exist.

t2_02edge
Input{"A":[[2,2]],"B":[[2,2]]}
Expected[[2,2]]

Single-point intervals intersect exactly at [2,2].

t2_03edge
Input{"A":[[1,2],[3,4]],"B":[[5,6],[7,8]]}
Expected[]

Intervals in B are completely after intervals in A, so no intersections.

t3_01corner
Input{"A":[[1,5],[10,14],[16,18]],"B":[[2,6],[8,10],[11,20]]}
Expected[[2,5],[10,10],[11,14],[16,18]]

Tests correct handling of multiple overlapping intervals and pointer advancement.

t3_02corner
Input{"A":[[1,3],[5,7],[9,11]],"B":[[2,4],[6,8],[10,12]]}
Expected[[2,3],[6,7],[10,11]]

Tests correct intersection detection when intervals partially overlap and are interleaved.

t3_03corner
Input{"A":[[1,2],[3,4],[5,6]],"B":[[1,10]]}
Expected[[1,2],[3,4],[5,6]]

Tests confusion between 0/1 and unbounded intervals; B covers all A intervals.

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(m+n) two-pointer solution performance within 2 seconds.

Practice

(1/5)
1. You are given a list of meeting time intervals represented as pairs of start and end times. You need to determine if a single person can attend all meetings without any overlaps. Which approach guarantees an optimal and efficient solution?
easy
A. Use dynamic programming to find the maximum number of non-overlapping intervals.
B. Sort intervals by start time and check for any overlap by comparing each interval's start with the previous interval's end.
C. Use a brute force nested loop to compare every pair of intervals for overlap.
D. Sort intervals by end time and greedily select intervals that finish earliest to maximize the number of meetings attended.

Solution

  1. Step 1: Understand the problem requirement

    The problem asks if a single person can attend all meetings without overlap, so we must check if any intervals overlap.
  2. Step 2: Identify the correct approach

    Sorting intervals by start time and checking if any interval starts before the previous one ends guarantees detection of overlaps efficiently.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sorting by start time and checking overlaps is the standard approach [OK]
Hint: Sort by start time and check overlaps [OK]
Common Mistakes:
  • Confusing sorting by end time with start time for overlap detection
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. Consider the following code snippet implementing the sweep line algorithm to find the minimum number of platforms required. What is the value of max_platforms returned for the input arrivals = [900, 940, 950] and departures = [910, 1200, 1120]?
easy
A. 4
B. 1
C. 3
D. 2

Solution

  1. Step 1: Create and sort events

    Events: (900,1), (940,1), (950,1), (910,-1), (1200,-1), (1120,-1). Sorted: (900,1), (910,-1), (940,1), (950,1), (1120,-1), (1200,-1).
  2. Step 2: Sweep through events updating platforms_needed and max_platforms

    At 900 arrival: platforms_needed=1, max=1; at 910 departure: platforms_needed=0; at 940 arrival: platforms_needed=1; at 950 arrival: platforms_needed=2, max=2; at 1120 departure: platforms_needed=1; at 1200 departure: platforms_needed=0.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Maximum concurrent trains is 2 [OK]
Hint: Sort events and track increments/decrements [OK]
Common Mistakes:
  • Misordering events when arrival and departure times are close
  • Off-by-one errors in counting platforms
  • Ignoring departure before arrival at same time
4. The following code attempts to count intervals containing each point using a line sweep. Identify the bug that causes incorrect counts for points exactly at interval ends.
medium
A. Line adding interval end event should use end + 1 instead of end.
B. Sorting key should sort points before interval starts.
C. Active count should be incremented after processing points, not before.
D. Result array initialization size is incorrect.

Solution

  1. Step 1: Identify event creation for interval ends

    Interval end events use 'end' instead of 'end + 1', so points exactly at interval end are processed after the interval ends.
  2. Step 2: Understand effect on counting

    Because end events are processed at 'end', points at 'end' see active count after decrement, missing that interval.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Changing to end + 1 fixes counting for points at interval ends [OK]
Hint: Interval end event must be at end+1 to include points at end [OK]
Common Mistakes:
  • Using end instead of end+1
  • Misordering events
  • Incorrect active count update
5. What is the time complexity of the optimal sweep line algorithm for Employee Free Time, given N total intervals across all employees?
medium
A. O(N log N) due to sorting all interval endpoints
B. O(N log M) where M is number of employees
C. O(N) because each interval is processed once
D. O(N²) due to nested iteration over intervals

Solution

  1. Step 1: Identify main operations

    We create 2N events (start and end per interval) and sort them.
  2. Step 2: Sorting events dominates complexity

    Sorting 2N events takes O(N log N). The sweep through events is O(N).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates, so O(N log N) [OK]
Hint: Sorting interval endpoints dominates time complexity [OK]
Common Mistakes:
  • Assuming linear time because each interval processed once
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