Set Intersection Size At Least Two

hard greedy sorting intervals

Problem

Given a list of closed intervals, find the smallest set S such that every interval contains at least two integers from S.

Inputintervals=[[1,3],[3,7],[8,9]]

Output5

One valid set is {1,2,3,7,8,9}; minimum size 5.

input

def intersectionSizeTwo(intervals):
    intervals.sort(key=lambda x: (x[1], -x[0]))
    a = b = -1
    ans = 0
    for s, e in intervals:
        if s > b:
            ans += 2
            b, a = e, e-1
        elif s > a:
            ans += 1
            a, b = b, e
    return ans

function intersectionSizeTwo(intervals) {
  intervals.sort((x,y) => x[1]-y[1] || y[0]-x[0]);
  let a = -1, b = -1, ans = 0;
  for (const [s, e] of intervals) {
    if (s > b) { ans += 2; b = e; a = e-1; }
    else if (s > a) { ans += 1; a = b; b = e; }
  }
  return ans;
}

int intersectionSizeTwo(int[][] intervals) {
    Arrays.sort(intervals, (x,y) -> x[1]!=y[1] ? x[1]-y[1] : y[0]-x[0]);
    int a = -1, b = -1, ans = 0;
    for (int[] iv : intervals) {
        int s = iv[0], e = iv[1];
        if (s > b) { ans += 2; b = e; a = e-1; }
        else if (s > a) { ans += 1; a = b; b = e; }
    }
    return ans;
}

int intersectionSizeTwo(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& x, auto& y){
        return x[1] != y[1] ? x[1] < y[1] : x[0] > y[0];
    });
    int a = -1, b = -1, ans = 0;
    for (auto& iv : intervals) {
        int s = iv[0], e = iv[1];
        if (s > b) { ans += 2; b = e; a = e-1; }
        else if (s > a) { ans += 1; a = b; b = e; }
    }
    return ans;
}

Explanation

We must pick a set of integers S so that every interval contains at least two of them, using as few numbers as possible. The clever move is to sort intervals by their right end (ascending), breaking ties by start descending, and then process them while remembering only the two largest points we have placed so far.

Why the right end? When we are forced to add points, picking the largest possible values (closest to the current interval's end) gives those points the best chance to also fall inside later intervals, which all end further right.

We track two numbers, a and b, the two biggest chosen points (with a < b). For each interval [s, e]: if its start is beyond b, neither chosen point helps, so we add the two rightmost values e-1 and e. If the start is beyond a but not b, one point already covers it, so we add just one point, e. Otherwise both points already lie inside, and we add nothing.

Example: [[1,3],[3,7],[8,9]]. For [1,3] add 2,3 (ans=2). For [3,7], start 3 is covered by 3 but not two points, so add 7 (ans=3). For [8,9] nothing is covered, add 8,9 (ans=5).

Because we always extend with the largest legal values, the total count of 5 is the minimum possible.

Time: O(n log n) Space: O(1)