757. Set Intersection Size At Least Two

Description

Solution

Refer to 452 452. Minimum Number of Arrows to Burst Balloons. These two questions are very similar.

We need to greedily find the maximum non-overlapping intervals.

And the template should always sort the intervals by endpoints and see if we could pick elements greedily to fit the requirement.

Code

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int> & a, vector<int> &b){
            if(a[1] == b[1]){
                return a[0] < b[0];
            }
            return a[1] < b[1];
        });
        vector<int> res = {intervals.front()[1] -1 , intervals.front()[1]};
        for(int i = 1; i < intervals.size(); i++){
            if(intervals[i][0] == res.back()){
                //need to add one element to satisfy the requirement
                res.push_back(intervals[i][1]);
            }else if(intervals[i][0] < res.back()){
                if(intervals[i][0] > res[res.size() - 2]){
                    //need to add one element to satisfy the requirement
                    res.push_back(intervals[i][1]);
                }
            }else{
                //need to add two elements to satisfy the requirement
                res.push_back(intervals[i][1] - 1);
                res.push_back(intervals[i][1]);
            }
        }
        return res.size();
    }
};