AlgoPressAppearance
0056-合并区间
https://leetcode.cn/problems/merge-intervals
以数组 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 <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4
思路
第一步将所有的区间按照start进行升序排列 第二步, 将第一个区间加入数组 第三步，如果下一个区间左边界 < list中最后一个区间的右边届，则直接更新list中的最右边界 如果下一个区间的左边界 > list的右边接，那么说明后面的数字都是大于这个右边界的，必须开辟一个新的区间
注意：排序是按照开头的位置排序，不是按照 end 位置排序 如果按照 end 位置排序，就从后往前处理
注意取区间下限的时候，要取 Max ，因为前面一段的长度有可能比后面的还长
参考代码
csharp
public class Solution {
public int[][] Merge(int[][] intervals) {
//按照头部排序
Array.Sort(intervals, (p1,p2) =>{
if( p1[0] > p2[0]){
return 1;
}
else if(p1[0] < p2[0]){
return -1;
}
else{
return 0;
}
});
List<List<int>> result = new List<List<int>>();
List<int> curRange = new List<int>();
curRange.Add(intervals[0][0]);
curRange.Add(intervals[0][1]);
result.Add(curRange);
for(int i=1; i<intervals.Length; i++){
if(intervals[i][0] <= curRange[1]){
curRange[1] = Math.Max(intervals[i][1],curRange[1]);
}
else{
curRange = new List<int>();
curRange.Add(intervals[i][0]);
curRange.Add(intervals[i][1]);
result.Add(curRange);
}
}
return result.Select(a => a.ToArray()).ToArray();
}
}
参考代码：复习 20220322
csharp
public class Solution {
public int[][] Merge(int[][] intervals) {
//排序左节点
Array.Sort(intervals,(a,b)=>{
return a[0].CompareTo(b[0]);
});
List<IList<int>> result = new List<IList<int>>();
//遍历
int start = intervals[0][0];
int end = intervals[0][1];
for(int i=1; i<intervals.Length; i++){
//Console.WriteLine("checking i={0},end={1}",i,end);
if(intervals[i][0] > end){ //分段
//Console.WriteLine("hit i={0}",i);
result.Add(new List<int>(){start,end});
//设置新起点
start = intervals[i][0];
end = intervals[i][1];
}
else{
end = Math.Max(end,intervals[i][1]);
}
}
//添加最后一段
result.Add(new List<int>(){start,end});
//抓换为输出数组
int[][] arr = new int[result.Count][];
for(int i=0; i<arr.Length; i++){
arr[i] = new int[]{result[i][0],result[i][1]};
}
return arr;
}
}