区间合并算法

第一步：按区间左端点排序
第二步：遍历每个区间，并维护一个当前区间的l和r，如果当前区间是个全新的区间（毫无交集），则把l和r更新为当前区间，如果不是全新的区间，则更新r。

例题：acwing区间合并
得到区间合并后的区间个数：

import java.util.*;class Main{ static int N = 100010; static List arr = new ArrayList<>(); public static int merge(List arr){ arr.sort(new Comparator(){ @Override public int compare(int[] o1,int[] o2){ return o1[0] - o2[0]; } }); int k = 0; int r = Integer.MIN_VALUE; for(int[] a : arr){ if(a[0] > r){//这是个全新的区间，和当前区间没有交集 k++; } r = Math.max(r, a[1]);//更新当前区间的右区间，无论这是个全新区间还是需要合并的区间 } return k; } public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); for(int i = 0; i < n; i++){ arr.add(new int[]{in.nextInt(), in.nextInt()}); } int cnt = merge(arr); System.out.println(cnt); }}

上面的代码只是计数，如果要返回合并后的区间，可以再定义一个区间的左端点，在遍历过程中，当左右端点确定下来之后，直接存下来，具体操作如下：

public static int merge(ArrayList list){ ArrayList res = new ArrayList<>(); list.sort(new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o1[0] - o2[0]; } }); int l = Integer.MIN_VALUE; int r = Integer.MIN_VALUE; for (int[] a : list) { //下一个区间左端点大于老区间右端点 if (a[0] > r){ //找到了新区间，就将老区间添加(不直接加新区间，因为新区间右端点还没确定) if (l != Integer.MIN_VALUE){ res.add(new int[]{l,r}); } l = a[0]; r = a[1]; }else {//更新当前区间的右侧区间 r = Math.max(r, a[1]); } } //最后一个合并区间,判断条件防止list为空 if (l != Integer.MIN_VALUE){ res.add(new int[]{l,r}); } return res.size(); }