贪心算法（13）（java）归并区间
标题：以数组 intervals 表现多少个区间的集合，此中单个区间为 intervals = 。请你归并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
<strong>输入：</strong>intervals = [,,,]
<strong>输出：</strong>[,,]
<strong>解释：</strong>区间 和 重叠, 将它们合并为 . 解法：
1.排序：左端点或右端点排序；
2.根据排序后的结果，总结规律，进而得出解决这个问题的计谋；
3.贪心计谋：求并集
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class Solution {
public int[][]merge(int[][]intervals)
{
//按左端点排序
Arrays.sort(intervals, Comparator.comparingInt(v -> v));
//合并区间，求并集
int left=intervals,right=intervals;
List<int[]>ret=new ArrayList<>();
for(int i=1;i<intervals.length;i++)
{
int a=intervals,b=intervals;
if(a<=right)//有重叠部分
{
right=Math.max(right,b);
}
else//不能合并
{
ret.add(new int[]{left,right});
left=a;
right=b;
}
}
ret.add(new int[]{left,right});
return ret.toArray(new int[]);
}
public static void main(String[] args) {
Solution solution=new Solution();
int [][]intervals=new int[][]{
new int[]{1,3},
new int[]{2,6},
new int[]{8,10},
new int[]{15,18},
};
int [][] merged=solution.merge(intervals);
for(int[] interval:merged)
{
System.out.println(Arrays.toString(interval));
}
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]