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.

💡 Fun fact: in the two-pointer pass, the decision of which pointer to advance has a one-line proof. Whichever interval ends first cannot possibly overlap anything later in the other list, because every later interval starts after this one's end. So it is finished, permanently, and advancing it can never skip an intersection. That single observation is what makes an O(m + n) pass correct where a nested loop would be O(mn).

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

The one-line idea: in both problems the interval that ends first is the one whose fate is already decided — so advance it, or serve it, and never look back.

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 — [5,5] — is a real intersection and the problem wants it.

There is no merging and no sorting. Both inputs arrive sorted and internally disjoint, and the pass depends on exactly that.

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

intervals.sort(key=lambda x: (x[1], -x[0]))        # end ↑, start ↓
ans = []
for s, e in intervals:
    if not ans or ans[-1] < s:                     # no chosen point inside
        ans += [e - 1, e]
    elif ans[-2] < s:                              # only the largest is inside
        ans.append(e)
return len(ans)

Because intervals are processed by ascending end, ans stays sorted, so ans[-1] and ans[-2] are the two largest points chosen so far — the only two that could possibly fall inside the current interval. That is why counting "how many points already hit this interval" costs two comparisons rather than a scan.

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 widest is processed first. Its two points then sit as far right as that interval allows, and the narrower intervals nested inside are likelier to already be covered.

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

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

[1,3]   ans is empty                    → add 2 and 3      ans = [2, 3]
[3,7]   ans[-1] = 3 ≥ 3, so one point is inside
        ans[-2] = 2 < 3, so only one   → add 7            ans = [2, 3, 7]
[8,9]   ans[-1] = 7 < 8, none inside    → add 8 and 9      ans = [2, 3, 7, 8, 9]

answer: 5

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 free here but decisive 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.

▶ 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.
Pattern: greedy with an exchange argument. Target: O(n log n) time, O(1) extra space.

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, which costs extra points when several intervals share an end.
• 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.

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