Set Intersection Size At Least Two

Set Intersection Size At Least Two

What is this problem about?

The Set Intersection Size At Least Two interview question gives you a list of intervals. You need to find the smallest set S of integers such that every interval [a, b] contains at least two elements from S. Minimize the size of S. This is a greedy interval covering problem requiring careful selection of which integers to include in the shared set.

Why is this asked in interviews?

Uber and Drawbridge ask this HARD problem because it generalizes the interval point cover problem (where you need one element per interval) to require two elements per interval. The greedy strategy must be carefully adapted: sort intervals by right endpoint, and for each interval, add the minimum number of elements from its right side needed to satisfy the "at least two" requirement. This models fault-tolerant sensor coverage, redundant network monitoring, and dual-validation systems.

Algorithmic pattern used

The pattern is greedy with sorting by right endpoint. Sort intervals by right endpoint; break ties by left endpoint descending (to handle identical right endpoints). Maintain the current set S. For each interval, check how many elements of S already lie within it. If 0 elements are covered: add right-1 and right to S. If exactly 1 element is covered: add right to S. If 2+ elements are covered: skip. This greedy ensures each new element covers as many future intervals as possible by choosing the rightmost possible values.

Example explanation

Intervals: [[1,3],[1,4],[2,5],[3,5]].

Sort by right, then left desc: [1,3],[1,4],[2,5],[3,5].

• [1,3]: S={}. 0 covered → add 2, 3. S={2,3}.
• [1,4]: S∩[1,4]={2,3} — 2 elements ✓ skip.
• [2,5]: S∩[2,5]={2,3} — 2 elements ✓ skip.
• [3,5]: S∩[3,5]={3} — 1 element → add 5. S={2,3,5}.

|S| = 3.

Common mistakes candidates make

• Using the same greedy as "interval point cover" (just adding the right endpoint once) — this misses the two-element requirement.
• Not sorting by right endpoint first — greedy interval problems almost always require right-endpoint sorting.
• Not checking how many elements of S are already in the current interval before deciding what to add.
• Off-by-one when adding right-1 and right — these must both be within [left, right], so right-1 >= left.

Interview preparation tip

For the Set Intersection Size At Least Two coding problem, the greedy array sorting interview pattern extends the classic interval cover to a two-point cover. The key insight: always add from the right side of each interval to maximize overlap with future (rightward) intervals. Uber interviewers test your ability to generalize from the one-element cover problem — explain the adaptation explicitly. Practice both the one-element and two-element variants to internalize the greedy pattern for interval covering problems.