Leetcode 56. Merge Intervals

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Version 1

/**
 * 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 size = intervals.size();
        vector<Interval> result;
        while(!intervals.empty()) {
            bool flag = true;
            for(int j = 1; j < intervals.size(); j++) {
                if(intervals[0].start <= intervals[j].end && intervals[0].end >= intervals[j].start) {
                    flag = false;
                    result.emplace_back(Interval(min(intervals[0].start, intervals[j].start), max(intervals[0].end, intervals[j].end)));
                    intervals.erase(intervals.begin() + j);
                    break;
                }
            }
            if(flag) {
                result.emplace_back(intervals[0]);
            }
            intervals.erase(intervals.begin());
        }
        if(size == result.size()) {
            return result;
        }
        else {
            return merge(result);
        }
    }
};

• Version 2

/**
 * 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) {
        vector<Interval> result;
        vector<int> flag(intervals.size(), 1);
        for(int i = 0; i < intervals.size(); i++) {
            if(!flag[i]) {
                continue;
            }
            for(int j = i + 1; j < intervals.size(); j++) {
                if(intervals[i].start <= intervals[j].end && intervals[i].end >= intervals[j].start) {
                    result.emplace_back(Interval(min(intervals[i].start, intervals[j].start), max(intervals[i].end, intervals[j].end)));
                    flag[i] = 0;
                    flag[j] = 0;
                    break;
                }
            }
            if(flag[i]) {
                result.emplace_back(intervals[i]);
                flag[i] = 0;
            }
        }
        if(intervals.size() == result.size()) {
            return result;
        }
        else {
            return merge(result);
        }
    }
};

Reference

1. https://leetcode.com/problems/merge-intervals/description/