Set Intersection Size At Least Two
Understanding the Problem
We have a collection of intervals, and we need to pick a set of integers such that every interval contains at least two of our chosen integers. The goal is to make this set as small as possible.
A useful way to frame it is placing pins on a number line. Each interval demands at least two pins inside it, and we want the fewest pins total. A single pin can serve several overlapping intervals at once, so placement matters. A pin near the right end of an interval is more reusable than one near the left, because intervals that we still have to handle tend to sit further to the right.
This leads to the strategy used below: process intervals in order of their right endpoint, and when an interval needs more pins, place them as far right as it allows. An interval that ends early is the most constrained, so handling it first and reusing its pins for later, wider intervals keeps the total small.
Key Constraints:
1 <= intervals.length <= 3000. With n up to 3000, an O(n^2) solution still runs in about 9 million operations and passes, but sorting plus one pass gives O(n log n).0 <= start_i < end_i <= 10^8. The value range is too large for a boolean array indexed by value. The algorithm has to work with interval endpoints, not iterate over every possible integer.
Approach 1: Brute Force (Enumerate All Subsets)
Intuition
Consider every possible set of integers and find the smallest one that satisfies the constraint. The candidates can be limited to integers that appear in at least one interval, since no other value helps. For each subset of those candidates, in increasing order of size, check whether every interval contains at least two elements from it, and return the first size that works.
This is impractical as a real solution. The value range goes up to 10^8, and even restricting to integers within intervals leaves an enormous search space. It does establish what kind of problem this is: a minimum set cover variant where each interval is a constraint that two chosen values must satisfy.
Algorithm
- Collect all unique integers that appear in at least one interval.
- Generate all subsets of these integers in order of increasing size.
- For each subset, check if every interval contains at least 2 elements from the subset.
- Return the size of the first valid subset found.
Visualization and Code
Loading animation...
- Time Complexity: O(2^V * n) where V is the total number of unique integers across all intervals, and n is the number of intervals. Completely infeasible for real inputs.
- Space Complexity: O(V) for storing the candidates.
Enumerating subsets is hopeless at this scale. The next approach processes intervals in a fixed order and decides greedily which numbers to pick, which removes the exponential search entirely.
Approach 2: Greedy with Sorting by Right Endpoint
Intuition
Intervals that end earliest are the most constrained. An interval ending at position 5 must hold two chosen numbers, all of which are at most 5. An interval ending at position 100 has far more room. Sorting by right endpoint handles the tight intervals first, while their right endpoints are still small.
Process intervals in that order. For each one, count how many already-chosen numbers fall inside it. If two or more do, it is satisfied and we move on. If one does, we add one number. If none do, we add two.
New numbers go as far right as the current interval allows. Because intervals are sorted by right endpoint, every interval still to come ends at this position or later, so a number placed at the right end of the current interval is the one most likely to also fall inside those later intervals.
Ties in the right endpoint are broken by larger left endpoint first, processing the narrower interval before the wider one with the same end. Any number that satisfies the narrower interval lies inside the wider one as well, so this ordering never wastes a pin.
Tracking only the two largest chosen numbers p1 and p2 is enough. The chosen numbers only ever grow, so the two largest are also the two most likely to land inside an interval whose right endpoint is the current one or larger. If p1 and p2 both fall short of an interval, no smaller chosen number can be inside it either.
Placing new numbers at end (and end - 1 when two are needed) is safe because every later interval has right endpoint >= end, so a value at end is never wasted on an interval that has already been processed and always remains a candidate for the ones ahead.
Algorithm
- Sort intervals by right endpoint ascending. For ties, sort by left endpoint descending.
- Track the two largest chosen numbers so far (call them
p1andp2, wherep1 < p2). Initialize both to -1. - For each interval
[start, end]: - If
start <= p1, bothp1andp2are inside this interval. Skip. - Else if
start <= p2, onlyp2is inside. Addend. Update:p1 = p2, p2 = end. Increment count by 1. - Else, neither is inside. Add
end - 1andend. Update:p1 = end - 1, p2 = end. Increment count by 2. - Return the total count.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n) where n is the number of intervals. Sorting takes O(n log n), and the single pass through the sorted intervals takes O(n).
- Space Complexity: O(1) extra space. We only track two variables
p1andp2regardless of input size.
This approach is optimal for the "at least two" requirement. The two-variable trick is specific to the number two. A version that asks for at least k elements per interval needs a different bookkeeping scheme, which the next approach provides.
Approach 3: Greedy with Explicit Set (Generalizable to k)
Intuition
This uses the same sort order but keeps an explicit sorted list of every chosen number instead of two variables. For each interval, two binary searches count how many chosen numbers fall inside it. If fewer than two do, the missing numbers are inserted at the rightmost positions the interval allows.
The benefit is generalization: replacing the constant 2 with k solves the "at least k" version with no other change, because the count-and-fill logic does not depend on the target being two. The cost is a higher running time, since inserting into a sorted array shifts elements and can take O(n) per insertion.
Algorithm
- Sort intervals by right endpoint ascending, left endpoint descending for ties.
- Maintain a sorted list
chosenof all selected numbers. - For each interval
[start, end]: - Use binary search to count how many numbers in
chosenfall in[start, end]. - If the count is >= 2, skip this interval.
- If the count is 1, add
endtochosen(if not already present). - If the count is 0, add
end - 1andendtochosen. - Return the size of
chosen.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2) in the worst case. Sorting is O(n log n), but each insertion into the sorted list can take O(n) time due to shifting elements.
- Space Complexity: O(n) for the
chosenlist. In the worst case (all intervals are disjoint), we store 2n numbers.