LeetCode Daily Question 1

3 月 5 日 每日一题

题目：56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

eg: Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6]overlaps, merge them into [1,6].

思路

首先对 interval 进行排序,之后遍历 interval，如果该 interval 是第一个，或者当前的 merged 的尾部和当前 interval 没有相交，直接 push。反之对 merged 尾部的【1】进行修改。注意 A or B 的反为（A 反&B 反 ）
时间复杂度为 O(nlogn) 空间复杂度为 O(n)(sort)

代码

1
2
3
4
5
6
7
8
9
10
11

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b){return a[0] < b[0];});
        vector<vector<int>> merged;
        for(auto interval: intervals){
            if(merged.empty() || merged.back()[1] < interval[0])
                merged.push_back(interval);
            else
                merged.back()[1] = max(interval[1],merged.back()[1]);
        }
        return merged;
    }