C++(NlogN) greedy + binary_search


  • 0
    M
    const int N = 6000 + 10;
    class Solution {
        int a[N];
    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]; });
            int n = 0;
            for (auto e : intervals){
                //cout << "(" << e[0] << "," << e[1] << ")" << endl;
                if(n == 0 || e[0] > a[n - 1]){
                    a[n ++] = e[1] - 1;
                    a[n ++] = e[1];
                }
                else{
                    int l = 0, r = n - 1;
                    while(l < r){
                        int mid = l + ((r -l) >> 1);
                        if(a[mid] < e[0])
                            l = mid + 1;
                        else
                            r = mid;
                    }
                    if(n - l < 2){
                        a[n ++] = e[1];
                        int i = n - 1;
                        while(i - 1 >= 0 && a[i - 1] == a[i]){
                            a[i - 1] --; i--;
                        }
                    }
                    
                }
            }
            return n;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.