# 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.

Example 1:

``````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] overlap, merge them into [1,6].
``````

Example 2:

``````Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
``````

Constraints:

• `1 <= intervals.length <= 10^4`
• `intervals[i].length == 2`
• `0 <= starti <= endi <= 10^4`

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

starts: 1 2 8 15

ends: 3 6 10 18

``````class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<vector<int>> res;
vector<int> starts, ends;
for (int i = 0; i < n; ++i) {
starts.push_back(intervals[i][0]);
ends.push_back(intervals[i][1]);
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
for (int i = 0, j = 0; i < n; ++i) {
if (i == n - 1 || starts[i + 1] > ends[i]) {
res.push_back({starts[j], ends[i]});
j = i + 1;
}
}
return res;
}
};
``````

``````// Time Limit Exceeded
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
for (int i = 0; i < intervals.size(); ++i) {
res = insert(res, intervals[i]);
}
return res;
}
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int> newInterval) {
vector<vector<int>> res;
int n = intervals.size(), cur = 0;
for (int i = 0; i < n; ++i) {
if (intervals[i][1] < newInterval[0]) {
res.push_back(intervals[i]);
++cur;
} else if (intervals[i][0] > newInterval[1]) {
res.push_back(intervals[i]);
} else {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
}
}
res.insert(res.begin() + cur, newInterval);
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/56

Employee Free Time

Insert Interval

Meeting Rooms II

Meeting Rooms

Teemo Attacking

Range Module

Partition Labels

Interval List Intersections

Amount of New Area Painted Each Day

Longest Substring of One Repeating Character

Count Integers in Intervals

Divide Intervals Into Minimum Number of Groups

Determine if Two Events Have Conflict

Count Ways to Group Overlapping Ranges

Points That Intersect With Cars

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

https://leetcode.com/problems/merge-intervals/discuss/21242/C++-10-line-solution.-easing-understanding

https://leetcode.com/problems/merge-intervals/discuss/21223/Beat-98-Java.-Sort-start-and-end-respectively

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation