</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Interval Intersection

What is this?

Two problems that both start from sorted intervals and go in opposite directions. The first reads an overlap out of two lists in a single pass. The second builds the smallest set of points touching every interval at least twice, a greedy that is short to write and needs an argument to defend.

Read-or-build decision flow for interval intersection

Fun fact: in the two-pointer pass, the choice of which pointer to advance has a short proof. Whichever interval ends first cannot overlap anything later in the other list, because every later interval in that list starts after the other interval's end. So it is finished, and advancing it cannot skip an intersection. That observation is what makes an O(m + n) pass correct where a nested loop would be O(mn). When both intervals end at the same coordinate, advancing either one is correct.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


Core idea: in both problems, order by end and the interval that ends first is the one you can settle now. In the first problem you advance past it. In the second you serve it with points at its right edge.


1. Two pointers, one pass

i = j = 0
while i < len(A) and j < len(B):
    lo, hi = max(A[i][0], B[j][0]), min(A[i][1], B[j][1])
    if lo <= hi: out.append([lo, hi])          # non-empty overlap
    if A[i][1] < B[j][1]: i += 1               # A[i] is finished
    else: j += 1                               # B[j] is finished

lo <= hi rather than lo < hi is deliberate: the endpoints are closed, so an overlap of a single point, such as [5,5], is a real intersection and the problem wants it.

On a tie (A[i][1] == B[j][1]) the code advances j. That is safe: the next B interval starts after the shared end, so the next test finds no overlap and then advances i. It costs one extra step, never an intersection.

There is no merging and no sorting. Both inputs arrive sorted and internally disjoint, and the pass depends on exactly that. The code only takes max and min of coordinates and never adds or subtracts them, so overflow cannot happen. Time is O(m + n), extra space O(1) besides the output.

2. Late placement, and a tie-break that matters

intervals.sort(key=lambda x: (x[1], -x[0]))        # end asc, start desc
p1 = p2 = -1                                       # two largest chosen points
ans = 0
for s, e in intervals:
    if s <= p1:                                    # both points inside
        continue
    if s <= p2:                                    # only p2 is inside
        p1, p2 = p2, e
        ans += 1
    else:                                          # neither is inside
        p1, p2 = e - 1, e
        ans += 2
return ans

Because intervals are processed by ascending end, every chosen point is at most the current end. So p1 and p2, the two largest chosen points, are the only ones that can fall inside the current interval, and a point is inside exactly when it is at least s. Counting how many points already hit this interval costs two comparisons rather than a scan. Space is O(1) beyond the in-place sort.

Why place at e and e − 1? A point further right is inside every future interval that a point further left is inside, and possibly more. Placing as late as legality allows therefore never loses, which is the exchange argument the whole greedy rests on.

Why the descending start on ties? Among intervals sharing an end, the narrowest (largest start) goes first. Its points sit inside the wider ones too, so those add nothing. With start ascending the sweep can add the same point twice: on [[3,4],[4,7],[5,7],[7,8]], [4,7] adds 7, then [5,7] sees only 7 inside and adds 7 again, so the sweep returns 4 instead of the correct 5.


3. A 30-second worked example (covering greedy)

intervals = [[1,3], [3,7], [8,9]], already sorted by end.

Greedy worked example producing 5 points

The interesting step is the middle one. [3,7] already contains the point 3, so it needs exactly one more, and putting it at 7 rather than at 4 is no worse here and matters whenever another interval starts before 7 and ends after it.


4. Where you'll actually meet this

  • Calendar systems. Intersecting two people's free/busy lists is the two-pointer pass verbatim.
  • Media editing. Where two tracks' clip ranges overlap, computed without materialising either timeline.
  • Monitoring. Correlating two incident windows across sorted event streams.
  • Patrol and sensor placement. "Every window observed at least twice" is a genuine redundancy requirement.
  • Database range queries. Intersecting sorted index ranges is the same single pass.

5. Problems in this chapter

Interval List Intersections

All intersections of two sorted, disjoint interval lists. Emit [max(starts), min(ends)] when non-empty and advance whichever interval ends first.
Pattern: two pointers over sorted lists. Target: O(m + n) time, O(1) extra space beyond the output.

Set Intersection Size At Least Two

The smallest set of integers containing at least two from every interval. Sort by end ascending and start descending, then place points as late as each interval allows. The brute force is exponential in the coordinate range.
Pattern: greedy with an exchange argument. Target: O(n log n) time, O(1) extra space beyond the sort.


6. Common pitfalls

  • Merging the lists first. They are already sorted and disjoint; merging adds work and loses the structure.
  • Using lo < hi. Endpoints are closed, so a single-point overlap counts.
  • Advancing both pointers after emitting, which skips intersections with the interval that has not finished.
  • Sorting by start in the covering greedy. End ascending is what makes late placement safe.
  • Dropping the descending start tie-break. With start ascending, a point can be added twice when intervals share an end, giving 4 instead of 5 on [[3,4],[4,7],[5,7],[7,8]].
  • Placing points early. A later point dominates an earlier one for every future interval.
  • Scanning the chosen set to count coverage, when only the two largest points can be inside.
  • Treating a tie on end as a special case in the two-pointer pass. Advancing either pointer is correct.

7. Key takeaways

  1. The interval ending first is settled: that fact powers both algorithms.
  2. [max(starts), min(ends)] is the intersection; inverted means empty.
  3. Sorted input is the gift. Do not merge it away.
  4. Place greedy points as late as legality allows: later dominates earlier.
  5. The two largest chosen points are the only ones that can matter, which makes the coverage check O(1) and the space O(1) beyond the sort.
  6. A tie-break can be load-bearing. End ascending, start descending, and both are needed.
  7. Why interviewers like it: the code is short, so the entire evaluation is whether you can justify the sort key and the pointer move.

Order: Interval List Intersections → Set Intersection Size At Least Two.

Interval List Intersections

Core idea: You have two lists of intervals, each already sorted and internally disjoint, and you want every place where they overlap. Walk both with two pointers i (into A) and j (into B). For the current pair A[i] and B[j], their intersection is the single interval [max(A[i].start, B[j].start), min(A[i].end, B[j].end)]. Emit it only if start <= end (a real overlap, possibly a single touching point). Then advance the pointer whose interval ends first: if A[i].end < B[j].end, the interval A[i] is fully behind us and can't overlap anything further right in B, so do i += 1; otherwise j += 1. Each step retires one interval, so the sweep is O(m + n).


Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.