leetcode/56ZMergeIntervals

Merge Intervals

给定一个区间的集合, 合并所有重复的区间

my solution (12ms)

可以通过重新排序的形式来一步步合并, 比如:

start: 1 2 8 15

end: 3 6 10 18

其中 start 和 end 是经排序后的数组

从 1 开始, 如果接下来的开始下标小于当前的结束下标 (2 < 3)

那么, 就可以合并, 继续对比下一个. (8 < 6) 不成立, 那么第一个区间就出现了, 1-6

接下来从 8 开始, 继续以上步骤, 直至数组尾部, 这样算法的复杂度就是 O(n)

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
static const int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    return 0;
}();

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<int> start;
        vector<int> end;
        vector<Interval> ret;

        for (auto& it : intervals) {
            start.push_back(it.start);
            end.push_back(it.end);
        }

        sort(start.begin(), start.end());
        sort(end.begin(), end.end());

        size_t size = start.size();
        for (int i = 0; i < size; ) {
            int ti = i;

            for (int j = i++; ;) {
                if (j >= size || i >= size) {	// 这里应该可以少判断 j 的值
                    ret.push_back( {start[ti], end.back()} );
                    break;
                }
                else if (start[i] <= end[j]) {
                    ++i, ++j;
                } 
                else {
                    ret.push_back( {start[ti], end[j]} );
                    break;
                }
            }

        }

        return ret;
    }
};

代码如上, 应该还有可以优化的地方 (比如说外围 for 循环, 他仅仅就是一个保留 i 的作用)

结果还不错

the best solution (8ms)

static const int _ = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    std::vector<Interval> merge(std::vector<Interval>& Intervals) {
        const int IntervalNum = Intervals.size();
        if (IntervalNum < 2)
            return Intervals;

        std::sort(Intervals.begin(), Intervals.end(), 
                  [](const Interval &A, const Interval &B) {
                      return A.start < B.start;
                  });

        std::vector<Interval> Merged {Intervals[0]};
        for (int i = 1; i < IntervalNum; ++i) {
            const Interval &Curr = Intervals[i];
            Interval &LastMerged = Merged.back();
            // 完全被内含的区间会被跳过
            if (Curr.end <= LastMerged.end)
                continue;
			// 更新区间的最大值
            if (Curr.start <= LastMerged.end)
                LastMerged.end = Curr.end;
            else	// 下一个区间完全不在当前区间内, 不能合并. 压入当前区间, 继续执行
                Merged.push_back(Curr);
        }

        return Merged;
    }
};

他的排序是直接在 Intervals 进行, 并且只比对 start (也是, 我好像做了多余的比对)

想法大致是一样的, 但是细节不够好