56. Merge Intervals

qqiangwu

Follow

Feb 23, 2017 · 1 min read

Using induction. If range [0, k) is merged, how to cope with element A[k]. It’s trivial. The whole process cost O(n).

Wait… Is the input sorted? No. So we need sort it first. Then we have O(nlogn + n)

Can we not sort the input? Then in the induction step, finding the proper position for A[k] needs O(logn). If a shift is involved, O(n) is required.

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        std::vector<Interval> result;
        
        std::sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b){
            return a.start < b.start;
        });
        
        for (const auto interval: intervals) {
            if (result.empty()) {
                result.push_back(interval);
            } else {
                auto& prev = result.back();
                
                if (isOverlapped(prev, interval)) {
                    prev.end = std::max(prev.end, interval.end);
                } else {
                    result.push_back(interval);
                }
            }
        }
        
        return result;
    }
    
    bool isOverlapped(const Interval a, const Interval b) {
        return a.start <= b.start && b.start <= a.end;
    }
};