Set Intersection Size At Least Two
Problem
Given a list of intervals, find the minimum size of a set such that every interval contains at least two integers from that set.
- 1 ≤ intervals.length ≤ 3000
- intervals[i].length == 2
- 0 ≤ starti < endi ≤ 10⁸
Example
intervals = [[1,3],[1,4],[2,5],[3,5]]3Think of this as efficiently 'pinning' tasks on a timeline. We need 2 pins per task. 1. The algorithm sorts intervals by End Time Ascending (and Start Time Descending for ties). Sorted order: `[[1,3], [1,4], [3,5], [2,5]]`. 2. Processing `[1,3]`: We have no pins. We need 2. The greedy choice is to place them as late as possible to maximize overlap with future tasks. We place pins at `2` and `3`. (Set: `{2, 3}`). 3. Processing `[1,4]`: Our pins `{2, 3}` are both inside. Requirement met. Do nothing. 4. Processing `[3,5]`: Only pin `3` is inside. We need 1 more. Place it at the very end, `5`. (Set: `{2, 3, 5}`). 5. Processing `[2,5]`: Pins `{3, 5}` are inside. Requirement met. Result: 3.
Approach
Straightforward Solution
A brute-force approach would attempt to generate all subsets of integers within the range of the intervals and check if they satisfy the '2-point' condition. Given the range can go up to 10^8, this is computationally impossible.
Core Observation
To minimize the total points used, every point added must serve the maximum number of future intervals. Since intervals are processed from left to right (based on end time), the optimal position for any new point is the rightmost possible position (the end of the current interval), as this extends its 'reach' furthest into subsequent intervals.
Path to Optimal
The key recognition signals are 'intervals', 'minimum size', and 'overlap'. These indicate a Greedy approach based on sorting. The standard 'Activity Selection' pattern sorts by End Time. However, a naive sort fails on nested intervals like `[1, 5]` and `[2, 5]`. If we process `[1, 5]` first, we might pick points `{4, 5}` which satisfies both, OR `{1, 5}` which fails `[2, 5]`. The insight is to always process the *stricter* (shorter) constraint first. By sorting `[2, 5]` before `[1, 5]` (Start Time Descending tie-breaker), we ensure that satisfying the inner interval automatically satisfies the outer one.
Optimal Approach
1. Sort intervals by End Time Ascending. Tie-break with Start Time Descending. 2. Maintain variables `p1` and `p2` tracking the two largest points added so far. 3. Iterate through the sorted intervals. For each interval, check overlap with `p1` and `p2`. If 2 points overlap, continue. If 1 point overlaps, add `end`. If 0 points overlap, add `end-1` and `end`. Update `p1` and `p2` accordingly.
Time
O(N log N)
Sorting the intervals takes O(N log N). The subsequent pass checks each interval exactly once, performing O(1) operations per check.
Space
O(1)
O(1) auxiliary space. We only track the last two points (`p1`, `p2`) and a counter. We do not need to store the full set of points to determine the answer.
Pattern Spotlight
Greedy Algorithms (Interval Sorting)
When greedy decisions on intervals depend on overlaps, sort by End Time to linearize the timeline. Crucially, if End Times match, sort by Start Time *Descending* to process the most restrictive (shortest) intervals first.
Solution
| 1 | class Solution: |
| 2 | def intersectionSizeTwo(self, intervals: List[List[int]]) -> int: |
| 3 | intervals.sort(key=lambda x: (x[1], -x[0])) |
| 4 | |
| 5 | p1, p2 = -1, -1 |
| 6 | count = 0 |
| 7 | |
| 8 | for start, end in intervals: |
| 9 | if p1 >= start and p2 >= start: |
| 10 | continue |
| 11 | |
| 12 | if p2 >= start: |
| 13 | count += 1 |
| 14 | p1 = p2 |
| 15 | p2 = end |
| 16 | else: |
| 17 | count += 2 |
| 18 | p1 = end - 1 |
| 19 | p2 = end |
| 20 | |
| 21 | return count |
Step-by-Step Solution
Sort Intervals by 'Earliest Finish, Latest Start'
| 3 | intervals.sort(key=lambda x: (x[1], -x[0])) |
Objective
To order the intervals such that we handle the most constrained deadlines first.
Key Insight
Sorting by End Time (`x[1]`) allows us to make a greedy decision that is locally optimal (satisfying the current interval) and globally optimal (extending furthest right). The secondary sort by Start Time Descending (`-x[0]`) is the critical fix for **nested intervals**: it ensures that if interval A is inside interval B and they end together, we process the *inner* (A) first. Satisfying the stricter inner interval automatically satisfies the outer one.
Interview Quick-Check
Core Logic
The sort key `(x[1], -x[0])` orders by deadline, while prioritizing shorter/stricter intervals when deadlines clash.
Common Pitfalls & Bugs
Forgetting the negative sign on `x[0]` will cause the algorithm to fail on nested intervals like `[1,5]` and `[2,5]`.
Initialize State Trackers
| 5 | p1, p2 = -1, -1 |
| 6 | count = 0 |
Objective
To initialize the variables that track the locations of the two most recently placed points.
Key Insight
We don't need to store a generic array of points. We only care about the 'frontier'—the rightmost points that might overlap with the next interval. Initializing `p1` and `p2` to `-1` ensures they fall outside the range of any valid interval (since `start >= 0`), forcing the greedy logic to add points for the very first interval.
Interview Quick-Check
State & Boundaries
p1 and p2 act as a sliding window of 'active' points. p1 is the second-to-last point, p2 is the last point.
Execute Greedy Coverage Strategy
| 8 | for start, end in intervals: |
| 9 | if p1 >= start and p2 >= start: |
| 10 | continue |
| 12 | if p2 >= start: |
| 13 | count += 1 |
| 14 | p1 = p2 |
| 15 | p2 = end |
| 16 | else: |
| 17 | count += 2 |
| 18 | p1 = end - 1 |
| 19 | p2 = end |
Objective
To iterate through the sorted intervals and add the minimum number of points required to satisfy the 2-point overlap constraint.
Key Insight
The greedy choice property applies here: if we need to add points, we should always add them at the *very end* of the current interval (`end` and `end-1`). This places them as far right as possible, maximizing the probability that they will also lie inside the *next* interval (which, due to sorting, starts later). We handle three cases: completely covered (do nothing), partially covered (add 1), or uncovered (add 2).
Interview Quick-Check
Core Logic
We prioritize point placement at `end` and `end-1`. This maximizes the 'reach' into future intervals.
Complexity
This linear scan works because the sorting guarantees we never need to look back at previous intervals.
State & Boundaries
When updating `p2` to a new value, the old `p2` becomes `p1`. Maintaining this order is crucial for the logic `p1 < p2`.
Return Total Set Size
| 21 | return count |
Objective
To return the accumulated count of points added.
Key Insight
The `count` variable holds the minimum set size. Because we only added points when absolutely forced to (by the 2-point constraint) and always placed them optimally (furthest right), the result is guaranteed to be minimal.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
intervals.sort(key=lambda x: (x[1], -x[0]))Sort intervals by end time ascending, then start time descending.
This specific sort order is the engine of the solution; it linearizes the problem by deadline and handles nested intervals by processing the strictest constraint first.
p2 = endPlace the new point at the very end of the current interval.
This is the greedy choice that guarantees optimality; picking the rightmost possible point maximizes the chance of overlapping with the next interval.
p1 = end - 1Place the first new point at `end - 1`.
We pick `end - 1` instead of `start` because it is further right, offering better overlap potential while remaining distinct from `end`.
p2 = endPlace the second new point at `end`.
Just as in the 1-point case, placing a point at the absolute boundary maximizes its utility for future deadlines.
if p2 >= start:Check if the interval is partially covered (contains only p2).
This condition identifies the case where the previous 'last' point is inside, but the 'second to last' fell short, requiring exactly one new point.
p1 = p2Shift the last point (p2) to become the second-to-last point (p1).
This maintains the invariant that `p1` and `p2` always track the two rightmost points in our set.
if p1 >= start and p2 >= start:Check if the current interval is already fully covered by existing points.
If `p1` (the second-to-last point) is inside the interval, then `p2` (which is larger) is definitely inside too, satisfying the 2-point requirement.
else:Handle the case where no existing points cover the interval.
If even `p2` is to the left of `start`, the interval is completely disjoint from our current set, forcing us to add 2 new points.
p1, p2 = -1, -1Initialize the last two chosen points to -1.
Setting these to -1 guarantees they do not satisfy the first interval (min start 0), correctly triggering the initial point placement logic.
continueSkip processing if the interval is already satisfied.
Greedy minimality requires us to add nothing if the constraints are already met.
for start, end in intervals:Iterate through each interval in the sorted list.
A single linear pass is sufficient after sorting because the 'future' intervals are guaranteed to end later.
count += 1Increment the count by 1.
We add exactly the minimum necessary points to satisfy the constraint.
count += 2Increment the count by 2.
We must add two distinct points to satisfy the problem constraint for this disjoint interval.
return countReturn the calculated minimum set size.
After processing all intervals with optimal greedy choices, this count represents the global minimum.
count = 0Initialize the counter for the total points added.
This variable accumulates the answer as we make greedy decisions.
Test Your Understanding
Why is it sufficient to track only the last two points (`p1`, `p2`) instead of the entire set of chosen points?
Because we sort by End Time, any future interval must end *after* the current one. This implies its start time will likely be to the right of our older points. The only points with a chance of landing inside the next interval are the rightmost ones we just added.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Set Intersection Size At Least Two from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Set Intersection Size At Least Two drill