Problem Description

You are given a list of intervals, where each interval is represented as a pair [start, end] and includes every integer between start and end (inclusive). Your task is to select the smallest possible set of integers such that every interval contains at least two of the selected integers.

Key constraints:

• Each interval must have at least two elements from your chosen set.
• You cannot count the same integer for more than one interval unless it genuinely fits both intervals.
• There is always at least one valid solution.
• Input is a list of intervals: intervals.
• Output is an integer: the minimum size of the required set.

Example: For intervals = [[1,3], [1,4], [2,5], [3,5]], one possible answer is 3 (with the set {2, 3, 4}).

Thought Process

The brute-force way would be to try every possible subset of integers and see whether it covers all intervals with at least two elements each. However, this approach is computationally infeasible for larger inputs.

Instead, we want to be greedy: for each interval, we want to place our chosen numbers as "late" as possible, so that they can cover future intervals as well. By sorting the intervals and always picking the largest possible numbers within each interval, we maximize reuse.

The key insight is that, by processing intervals in a certain order and always ensuring the "latest" numbers are chosen, we avoid unnecessary duplication and minimize the total count.

Solution Approach

Let's break the algorithm into steps:

1. Sort the intervals: Sort the intervals by their end point (and, for ties, by start in descending order). This way, we process intervals that finish earliest first, maximizing the chance of reusing numbers.
2. Track the chosen set: Keep track of the numbers we've already selected (e.g., as a list or set).
3. Process each interval: For each interval, count how many numbers from our current set fall within it. If fewer than two, add the largest possible numbers from the interval (usually the end or end-1).
4. Greedy selection: Always pick the largest numbers available in the interval, as they are more likely to help with future intervals.
5. Repeat: Continue until all intervals are covered.

This approach ensures that each interval is satisfied with at least two elements, and that the chosen elements are reused as much as possible.

Example Walkthrough

Let's walk through the example intervals = [[1,3], [1,4], [2,5], [3,5]].

1. Sort intervals: After sorting by end, we get: [[1,3], [1,4], [2,5], [3,5]] (already sorted in this case).
2. First interval [1,3]: No numbers chosen yet, so we pick the two largest: 2 and 3. Set = {2, 3}.
3. Next interval [1,4]: Set {2, 3} already covers 2 and 3, both within [1,4]. So, already satisfied.
4. Next interval [2,5]: Set {2, 3} covers 2 and 3, both within [2,5]. Already satisfied.
5. Next interval [3,5]: Set {2, 3} covers 3 (but not 4 or 5). Only one covered, so we need one more. Pick 4 (the largest available in [3,5] not already chosen). Now set = {2, 3, 4}.
6. All intervals satisfied. The answer is 3.

Time and Space Complexity

Brute-force: Checking all subsets of possible integers is exponential, roughly O(2^N), and not feasible for large N.

Optimized (Greedy) Approach:

• Sorting the intervals: O(N log N), where N is the number of intervals.
• Processing each interval: O(N), since for each interval we do constant work (checking up to two numbers).
• Total time complexity: O(N log N).
• Space complexity: O(N), for storing the chosen set and the sorted intervals.

Summary

The "Set Intersection Size At Least Two" problem is elegantly solved by a greedy approach: sort intervals by their end, and for each, add the largest needed numbers to ensure every interval gets two. This minimizes the total set size and leverages overlap between intervals. The key insight is to always pick numbers as late as possible within each interval, maximizing their usefulness for future intervals and ensuring optimality.

Code Implementation

class Solution:
    def intersectionSizeTwo(self, intervals):
        intervals.sort(key=lambda x: (x[1], -x[0]))
        res = []
        for interval in intervals:
            cnt = 0
            # Count how many numbers in res are in the interval
            for num in reversed(res):
                if num >= interval[0]:
                    if num <= interval[1]:
                        cnt += 1
                    if cnt == 2:
                        break
            # Add missing numbers (at most 2)
            for x in range(interval[1] - (1 - cnt), interval[1] + 1):
                if x not in res and x >= interval[0]:
                    res.append(x)
        return len(res)
      

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
        });
        vector<int> res;
        for (const auto& interval : intervals) {
            int cnt = 0;
            for (int i = res.size() - 1; i >= 0; --i) {
                if (res[i] >= interval[0] && res[i] <= interval[1]) {
                    ++cnt;
                    if (cnt == 2) break;
                }
            }
            for (int x = interval[1] - (1 - cnt); x <= interval[1]; ++x) {
                if (find(res.begin(), res.end(), x) == res.end() && x >= interval[0])
                    res.push_back(x);
            }
        }
        return res.size();
    }
};
      

import java.util.*;

class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] != b[1] ? a[1] - b[1] : b[0] - a[0]);
        List<Integer> res = new ArrayList<>();
        for (int[] interval : intervals) {
            int cnt = 0;
            for (int i = res.size() - 1; i >= 0; --i) {
                int num = res.get(i);
                if (num >= interval[0] && num <= interval[1]) {
                    cnt++;
                    if (cnt == 2) break;
                }
            }
            for (int x = interval[1] - (1 - cnt); x <= interval[1]; x++) {
                if (!res.contains(x) && x >= interval[0]) {
                    res.add(x);
                }
            }
        }
        return res.size();
    }
}
      

var intersectionSizeTwo = function(intervals) {
    intervals.sort((a, b) => a[1] === b[1] ? b[0] - a[0] : a[1] - b[1]);
    let res = [];
    for (let interval of intervals) {
        let cnt = 0;
        for (let i = res.length - 1; i >= 0; --i) {
            let num = res[i];
            if (num >= interval[0] && num <= interval[1]) {
                cnt++;
                if (cnt === 2) break;
            }
        }
        for (let x = interval[1] - (1 - cnt); x <= interval[1]; ++x) {
            if (!res.includes(x) && x >= interval[0]) {
                res.push(x);
            }
        }
    }
    return res.length;
};