以数组 intervals
表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
注意:本题与主站 56 题相同: https://leetcode-cn.com/problems/merge-intervals/
区间合并,将所有存在交集的区间进行合并。
模板:
def merge(intervals):
res = []
intervals.sort(key=lambda x: x[0])
st = ed = -1
for s, e in intervals:
if ed < s:
if st != -1:
res.append([st, ed])
st, ed = e[0], e[1]
else:
ed = max(ed, e[1])
if st != -1:
res.append([st, ed])
return res
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
st = ed = -1
res = []
for s, e in intervals:
if ed < s:
if st != -1:
res.append([st, ed])
st, ed = s, e
else:
ed = max(ed, e)
if st != -1:
res.append([st, ed])
return res
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int st = -1, ed = -1;
List<int[]> res = new ArrayList<>();
for (int[] e : intervals) {
if (ed < e[0]) {
if (st != -1) {
res.add(new int[]{st, ed});
}
st = e[0];
ed = e[1];
} else {
ed = Math.max(ed, e[1]);
}
}
if (st != -1) {
res.add(new int[]{st, ed});
}
return res.toArray(new int[res.size()][]);
}
}
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>> &intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
int st = -1, ed = -1;
for (auto e : intervals)
{
if (ed < e[0])
{
if (st != -1)
{
res.push_back({st, ed});
}
st = e[0];
ed = e[1];
}
else
{
ed = max(ed, e[1]);
}
}
if (st != -1)
{
res.push_back({st, ed});
}
return res;
}
};
func merge(intervals [][]int) [][]int {
var res [][]int
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
st, ed := -1, -1
for _, e := range intervals {
if ed < e[0] {
if st != -1 {
res = append(res, []int{st, ed})
}
st, ed = e[0], e[1]
} else {
ed = max(ed, e[1])
}
}
if st != -1 {
res = append(res, []int{st, ed})
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
public class Solution {
public int[][] Merge(int[][] intervals) {
var res = new List<int[]>();
int st = -1, ed = -1;
foreach (var e in intervals.OrderBy(a => a[0]))
{
if (ed < e[0])
{
if (st != -1)
{
res.Add(new int[] { st, ed });
}
st = e[0];
ed = e[1];
}
else
{
ed = Math.Max(ed, e[1]);
}
}
if (st != -1)
{
res.Add(new int[] { st, ed });
}
return res.ToArray();
}
}