C++ 24ms solution


  • 0
    X
     class Solution {
        public:
            struct node{
                int flag;// 0 start 1 end;
                int val;
                node(int flag = -1, int val = -1){
                    this->flag = flag;
                    this->val = val;
                }
            };
            struct mycmp{
                bool operator()(const node& a, const node& b){
                    if(a.val == b.val){
                        return a.flag < b.flag;
                    }
                    return a.val < b.val;
                }
            };
            vector<Interval> merge(vector<Interval>& intervals) {
                vector<Interval> ans;
                vector<node> vec(intervals.size() * 2);
                for(int i = 0, count = 0;i < intervals.size(); ++i){
                    vec[count++] = node(0, intervals[i].start);
                    vec[count++] = node(1, intervals[i].end);
                }
                sort(vec.begin(), vec.end(), mycmp());
                for(int i = 0;i < vec.size(); ){
                    int start = i;
                    int end = i;
                    int count = 0;
                    while(end < vec.size()){
                        if(vec[end].flag == 0){
                            ++count;
                        }else{
                            --count;
                        }
                        if(count == 0){
                            ans.push_back(Interval(vec[start].val, vec[end].val));
                            break;
                        }
                        ++end;
                    }
                    i = end + 1;
                }
                return ans;
            }
        };

Log in to reply
 

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