The smallest intersection set you can get by taking k elements from n intervals

It is often the case that out of a number of groups, we desire to take a number of representatives. It is usually our goal to take the smallest number of representatives while making sure that no group is left out.

For our case study today we are going to see a simplified case.

We have a number of integer intervals [a, b] (for integers a < b). And we wish to find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has size at least 2.

In other words, we want to take two elements from each interval, and we want to make sure the number of elements we take is as small as possible. This can be achieved by leveraging the fact that some elements belong to multiple intervals.

Solution: A greedy approach

We sort the intervals by their end time, and take the last two elements of the interval, and get presented with 3 possible cases.

1. The next interval shares two elements with the current one: we don't add any new elements to the set.
2. The next interval shares one element: we add only one element
3. The next interval shares no elements with the next: we take two new elements.

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