区间问题就是线段问题，常见的问题设计就是合并区间、找出区间的交集等。
这类问题的技巧有：排序+画图。

  1. 排序：按照起点进行升序，相同则按照终点降序；
  2. 画图：两个区间的相对位置有哪些，不同的相对位置该怎么处理。

一、区间覆盖问题（LC1288, Medium, 删除被覆盖区间）

image.png
算出被覆盖区间的数目，然后总数一减就是要的结果，关键：排序+画图观察3种覆盖情况。

  1. class Solution {
  2.     public int removeCoveredIntervals(int[][] intervals) {
  3.         Arrays.sort(intervals, new Comparator<int[]>() {
  4.             @Override
  5.             public int compare(int[] o1, int[] o2) {
  6.                 return o1[0]==o2[0] ? o2[1]-o1[1] : o1[0]-o2[0];
  7.             }
  8.         });
  10.         int total = intervals.length; //总数
  11.         int res = 0; //覆盖区间的数目
  12.         int left = intervals[0][0];
  13.         int right = intervals[0][1];
  15.         for (int i=1; i<total; i++) {
  16.             int[] inter = intervals[i];
  17.             //三种情况
  18.             //1、被覆盖
  19.             if (left<=inter[0] && right>=inter[1]) {
  20.                 res++;
  21.             }
  22.             //2、合并有重叠区间
  23.             if (right<inter[1]) {
  24.                 right = inter[1];
  25.             }
  26.             //3、没有交集
  27.             if (inter[0] > right) {
  28.                 left = inter[0];
  29.                 right = inter[1];
  30.             }
  31.         }
  33.         return total-res;
  35.     }
  36. }

二、区间合并问题（LC56, Medium, 合并区间）

image.png

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         //排序
  4.         Arrays.sort(intervals, new Comparator<int[]>() {
  5.             public int compare(int[] interval1, int[] interval2) {
  6.                 return interval1[0] - interval2[0];
  7.             }
  8.         });
  9.         int m = intervals.length;
  10.         int left = intervals[0][0], right = intervals[0][1];
  11.         List<int[]> resList = new ArrayList<>();
  12.         for (int i=1; i<=m; i++) {
  13.             if (i == m) {
  14.                 resList.add(new int[] {left, right});
  15.                 //System.out.print(left + " " + right);
  16.                 break;
  17.             }
  18.             int[] inter = intervals[i];
  19.             //重叠合并
  20.             if (inter[0]>=left && inter[0]<=right) {
  21.                 right = Math.max(right, inter[1]);
  22.             }
  23.             if (inter[0] > right) {
  24.                 resList.add(new int[] {left, right});
  25.                 //System.out.print(left + " " + right);
  26.                 left = inter[0];
  27.                 right= inter[1];
  28.             }
  29.         }
  30.         return resList.toArray(new int[resList.size()][]);
  31.     }
  32. }

三、区间交集问题（LC986, Medium, 区间列表的交集 ）

image.png

  1. class Solution {
  2.     public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
  3.         List<int[]> resList = new ArrayList<>();
  4.         int i=0, j=0;
  5.         int m=firstList.length, n=secondList.length;
  6.         while (i<m && j<n) {
  7.             int a1 = firstList[i][0], a2 = firstList[i][1]; //第一个区间的第i个小区间
  8.             int b1 = secondList[j][0], b2 = secondList[j][1]; //第二个区间的第j个小区间
  9.             //存在交集
  10.             if (b2>=a1 && b1<=a2) {
  11.                 resList.add(new int[]{Math.max(a1, b1), Math.min(a2, b2)});
  12.             }
  13.             if (a2>b2) {
  14.                 j++;
  15.             } else {
  16.                 i++;
  17.             }
  18.         }
  19.         return resList.toArray(new int[resList.size()][]);
  20.     }
  21. }

总结一下，区间类问题看起来都比较复杂，情况很多难以处理，但实际上通过观察各种不同情况之间的共性可以发现规律，用简洁的代码就能处理。