Set Intersection Size At Least Two - Solution & Explanation

Problem Overview: You are given a list of intervals [start, end]. The goal is to build a set of integers such that every interval contains at least two numbers from that set. The challenge is minimizing the total size of the chosen set while satisfying all intervals.

Approach 1: Brute Force Interval Coverage (Exponential / Inefficient)

A straightforward idea is to try selecting numbers for each interval and check whether the global set satisfies the requirement. For every interval, you could attempt combinations of numbers inside its range and verify whether all intervals contain at least two selected values. This effectively becomes a combinatorial search problem. The number of possibilities grows rapidly because each interval may contain many candidate numbers.

This approach repeatedly checks intersections between intervals and the current set, leading to extremely high computational cost. In the worst case the complexity becomes exponential with respect to the range size or number of intervals. Space complexity is also large because you must store candidate selections. This method only helps build intuition about the constraint that every interval must contribute at least two elements.

Approach 2: Greedy Approach with Sorting (O(n log n) time, O(1) space)

The efficient strategy relies on a greedy observation: intervals that end earlier should be satisfied first. Sort the intervals primarily by their end value and secondarily by start in descending order. Processing intervals in this order ensures that when you pick numbers near the end of an interval, those numbers have the highest chance of satisfying upcoming intervals as well.

Maintain the last two selected elements that currently cover intervals. For each interval, check how many of these chosen numbers fall inside it. If both already lie inside the interval, nothing needs to be added. If only one lies inside, add the interval's end value to guarantee two elements. If none lie inside, add end-1 and end. Choosing numbers as far right as possible maximizes reuse for future intervals.

This greedy decision works because later intervals have equal or larger end points after sorting. Numbers placed near the end will likely remain valid for multiple intervals. Sorting costs O(n log n), while the scan through intervals is O(n). Only a few variables track the latest chosen values, so the extra space is O(1).

The technique combines sorting with a greedy strategy and interval reasoning similar to problems involving arrays and scheduling.

Recommended for interviews: Interviewers expect the greedy sorting solution. Brute force demonstrates understanding of the constraint, but the key signal of strong problem‑solving is recognizing that placing elements near interval ends maximizes reuse across intervals. The optimal solution runs in O(n log n) time with constant extra space and handles large input sizes efficiently.