贪心算法（13）（java）归并区间

标题：
以数组 intervals 表现多少个区间的集合，此中单个区间为 intervals = [starti, endi] 。请你归并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：

1. <strong>输入：</strong>intervals = [[1,3],[2,6],[8,10],[15,18]]
2. <strong>输出：</strong>[[1,6],[8,10],[15,18]]
3. <strong>解释：</strong>区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

复制代码

解法：
1.排序：左端点或右端点排序；
2.根据排序后的结果，总结规律，进而得出解决这个问题的计谋；
3.贪心计谋：求并集

1. import java.util.ArrayList;
2. import java.util.Arrays;
3. import java.util.Comparator;
4. import java.util.List;
6. public class Solution {
7.     public int[][]merge(int[][]intervals)
8.     {
9.         //按左端点排序
10.         Arrays.sort(intervals, Comparator.comparingInt(v -> v[0]));
11.         //合并区间，求并集
12.         int left=intervals[0][0],right=intervals[0][1];
13.         List<int[]>ret=new ArrayList<>();
14.         for(int i=1;i<intervals.length;i++)
15.         {
16.             int a=intervals[i][0],b=intervals[i][1];
17.             if(a<=right)//有重叠部分
18.             {
19.                 right=Math.max(right,b);
21.             }
22.             else//不能合并
23.             {
24.                 ret.add(new int[]{left,right});
25.                 left=a;
26.                 right=b;
28.             }
29.         }
30.         ret.add(new int[]{left,right});
31.         return ret.toArray(new int[0][]);
32.     }
34.     public static void main(String[] args) {
35.         Solution solution=new Solution();
36.         int [][]intervals=new int[][]{
37.                 new int[]{1,3},
38.                 new int[]{2,6},
39.                 new int[]{8,10},
40.                 new int[]{15,18},
42.         };
43.         int [][] merged=solution.merge(intervals);
44.         for(int[] interval:merged)
45.         {
46.             System.out.println(Arrays.toString(interval));
47.         }
48.     }
50. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。