题解 | #合并区间#

/**
 * struct Interval {
 *  int start;
 *  int end;
 *  Interval(int s, int e) : start(start), end(e) {}
 * };
 */
#include <algorithm>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类vector
     * @return Interval类vector
     */

    vector<Interval> merge(vector<Interval>& intervals) {
        // write code here
        vector<Interval> res;

        // 判断特殊情况intervals为空或者只有一个数据时
        if (intervals.size() == 0 || intervals.size() == 1) {
            return intervals;
        }

        // 先排序，再进行合并
        sort(intervals.begin(), intervals.end(), [](const Interval & p1, const Interval & p2) {
            return p1.start < p2.start;
        });

        // 先放第1个数据到res中
        res.push_back(intervals[0]);
        int flage = 0;

        // 循环判断intervals中剩余的数据是否可以合并
        for (int i = 1; i < intervals.size(); i++) {
            flage = 0;

            // 循环判断和res中的数据是否可以合并
            for (int j = 0; j < res.size(); j++) {

                // 可以合并的情况1
                if (intervals[i].start >= res[j].start && intervals[i].start <= res[j].end) {
                    if (intervals[i].end > res[j].end) {
                        res[j].end = intervals[i].end;
                    }
                    // 标志变量至1
                    flage = 1;
                }

                // 可以合并的情况2
                if (intervals[i].end <= res[j].end && intervals[i].end >= res[j].start) {
                    if (intervals[i].start < res[j].start) {
                        res[j].start = intervals[i].start;
                    }
                    // 标志变量至1
                    flage = 1;
                }
            }

            // 没有合并的情况就push到intervals中
            if (flage == 0) {
                res.push_back(intervals[i]);
            }
        }

        // 合并之后再对res排序
        sort(res.begin(), res.end(), [](const Interval & p1, const Interval & p2) {
            return p1.start < p2.start;
        });

        // 返回res
        return res;
    }


};