56. Merge Intervals

扫描线版本很清晰 O(nlogn) time O(n) space

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        map<int, int> m; // 扫一遍输入intervals把start和end存到map里
        for (const auto &i : intervals) {
            ++m[i.start];
            --m[i.end];
        }
        vector<Interval> res;
        int cnt = 0;
        int b = 0;
        for (const auto &p : m) { // 扫一遍map并实时统计区间个数
            if (cnt == 0) { // 扫当前时刻之前如果区间为0，则当前时刻是区间的开始
                b = p.first;
            }
            cnt += p.second;
            if (cnt == 0) { // 扫当前时刻之后如果区间为0，则当前时刻是区间的结束
                res.push_back({b, p.first});
            }
        }
        return res;
    }
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        map<int, int> m;
        for (const auto &i : intervals) {
            ++m[i.start];
            --m[i.end];
        }
        int cnt = 0;
        int s = INT_MAX;
        vector<Interval> res;
        for (const auto &p : m) {
            s = min(s, p.first);
            cnt += p.second;
            if (cnt == 0) {
                res.emplace_back(s, p.first);
                s = INT_MAX;
            }
        }
        return res;
    }
};

greedy O(nlogn) time O(1) space

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals));
        vector<vector<int>> res{intervals[0]};
        for (const auto &i : intervals) {
            if (i[0] <= res.back()[1]) {
                res.back()[1] = max(res.back()[1], i[1]);
            } else {
                res.push_back(i);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        sort(begin(intervals), end(intervals));
        int n = intervals.size();
        vector<vector<int>> res{intervals[0]};
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] <= res.back()[1]) {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            } else {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        auto cmp = [](const Interval &lhs, const Interval &rhs) { return lhs.start < rhs.start; };
        sort(intervals.begin(), intervals.end(), cmp);
        vector<Interval> res;
        for (const auto &i : intervals) {
            if (!res.empty() && i.start <= res.back().end) {
                res.back().end = max(res.back().end, i.end);
            } else {
                res.push_back(i);
            }
        }
        return res;
    }
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        int n = intervals.size();
        if (n == 0) return {};
        sort(intervals.begin(), intervals.end(), [](const Interval &lhs, const Interval &rhs)
        { return lhs.start < rhs.start; }); // 切记不要加别的条件
        vector<Interval> res{intervals[0]};
        for (int i = 1; i < n; ++i) {
            if (res.back().end >= intervals[i].start) {
                res.back().end = max(res.back().end, intervals[i].end); // 这里一定要用max比如[1,4],[2,3]这个反例
            } else {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const Interval &lhs, const Interval &rhs)
        { return lhs.start < rhs.start; });
        int n = intervals.size();
        intervals.push_back(Interval(INT_MAX, INT_MAX));
        vector<Interval> res;
        for (int i = 0; i < n;) {
            int s = intervals[i].start;
            int e = intervals[i].end;
            int j = i + 1;
            for (; j < n && e >= intervals[j].start; ++j) {
                e = max(e, intervals[j].end);
            }
            res.emplace_back(s, e);
            i = j;
        }
        return res;
    }
};