How to Solve LeetCode 757: Minimum Set Intersection of Size Two with a Greedy Approach

Interview "Traps"

When interview questions become overly detailed, candidates may perceive a lower chance of success; longer interviews often indicate the interviewer's genuine interest, yet the correlation between interview length and hiring outcome is not straightforward.

Factors such as high competition and rising hiring thresholds can make thorough questioning seem like a barrier, while companies also monitor interview efficiency to avoid excessive time spent on unsuitable candidates.

Problem Description

Platform: LeetCode

Problem 757 – Minimum Set Intersection of Size Two

Given a list of integer intervals, find the smallest set S such that each interval contains at least two elements from S. Output the size of S.

Greedy Solution

The goal is to minimize the number of selected points, not to form a continuous segment. By sorting intervals first by increasing right endpoint and then by decreasing left endpoint, we can process them sequentially while maintaining the two largest selected points (variables a and b). Depending on the relationship between the current interval and these points, we add either two new points, one new point, or none.

class Solution {
    public int intersectionSizeTwo(int[][] ins) {
        Arrays.sort(ins, (a, b) -> {
            return a[1] != b[1] ? a[1] - b[1] : b[0] - a[0];
        });
        int a = -1, b = -1, ans = 0;
        for (int[] i : ins) {
            if (i[0] > b) {
                a = i[1] - 1;
                b = i[1];
                ans += 2;
            } else if (i[0] > a) {
                a = b;
                b = i[1];
                ans++;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& ins) {
        sort(ins.begin(), ins.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] != b[1] ? a[1] < b[1] : a[0] > b[0];
        });
        int a = -1, b = -1, ans = 0;
        for (const auto& i : ins) {
            if (i[0] > b) {
                a = i[1] - 1;
                b = i[1];
                ans += 2;
            } else if (i[0] > a) {
                a = b;
                b = i[1];
                ans++;
            }
        }
        return ans;
    }
};

class Solution:
    def intersectionSizeTwo(self, ins: List[List[int]]) -> int:
        ins.sort(key=lambda x: (x[1], -x[0]))
        a, b, ans = -1, -1, 0
        for i in ins:
            if i[0] > b:
                a, b = i[1] - 1, i[1]
                ans += 2
            elif i[0] > a:
                a, b = b, i[1]
                ans += 1
        return ans

function intersectionSizeTwo(ins: number[][]): number {
    ins = ins.sort((a, b) => {
        return a[1] !== b[1] ? a[1] - b[1] : b[0] - a[0];
    });
    let a = -1, b = -1, ans = 0;
    for (const i of ins) {
        if (i[0] > b) {
            a = i[1] - 1;
            b = i[1];
            ans += 2;
        } else if (i[0] > a) {
            a = b;
            b = i[1];
            ans++;
        }
    }
    return ans;
}

Time Complexity: O(n log n) for sorting, where n is the number of intervals.

Space Complexity: O(1) extra space besides the input array.