对力扣的区间类题目做一个总结！

合并区间

1 算法思想

1. 按照区间起点升序排序

   //按照区间起始位置排序
   /**
           如果v1[0]-v2[0]为正，代表v1与v2交换位置，故这是升序排序
           */
   Arrays.sort(intervals,(v1,v2)->v1[0]-v2[0]);
   

1. 设定start与end指针，首先初始化为第一个区间的两端值

   int start = intervals[0][0];
   int end = intervals[0][1];
   

1. 循环遍历，如果当前的end大于下一个区间的起点，那么说明两个区间有交集了，end更新，更新策略为当前end与下一个区间终点的最大值

   List<int[]>ans = new LinkedList<>();
   for(int i = 1;i<intervals.length;i++){
       if(end>=intervals[i][0]){
           end = Math.max(end,intervals[i][1]);
       }
       else{
           ans.add(new int[]{start,end});
           start = intervals[i][0];
           end = intervals[i][1];
       }
   }
   

2. 最后一步由于start与end圈区间的未加入最后结果，再次更新一次

   //最后一个区间加一下
   ans.add(new int[]{start,end});
   int[][]res = new int[ans.size()][2];
   return ans.toArray(res);
   

2 完整代码

class Solution {
    public int[][] merge(int[][] intervals) {
        //0 特殊情况处理
        if(intervals.length<=1){
            return intervals;
        }
        //1 按照区间起始位置排序
        /**
        如果v1[0]-v2[0]为正，代表v1与v2交换位置，故这是升序排序
        */
        Arrays.sort(intervals,(v1,v2)->v1[0]-v2[0]);
        //2 设定start end指针
        int start = intervals[0][0];
        int end = intervals[0][1];
        //3 循环算法策略
        List<int[]>ans = new LinkedList<>();
        for(int i = 1;i<intervals.length;i++){
            if(end>=intervals[i][0]){
                end = Math.max(end,intervals[i][1]);
            }
            else{
                ans.add(new int[]{start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        //4 最后一个区间加一下
        ans.add(new int[]{start,end});
        int[][]res = new int[ans.size()][2];
        return ans.toArray(res);
    }
}

无重叠区间

1 算法思想

  本质与合并区间没有什么不同，这里是求没有重叠区间的数目，那么在end指针的更新策略不是取最大，而是取最小。

区别在第3步

1. 循环遍历，如果当前的end大于下一个区间的起点，那么说明两个区间有交集了，end更新，更新策略为当前end与下一个区间终点的最大值

List<int[]>ans = new LinkedList<>();
for(int i = 1;i<intervals.length;i++){
    //>=号也要变成>,因为区间刚好相“切”是表明不重叠
    if(end>intervals[i][0]){
        //这里换成min
        //当前end大于下一个区间的起点，那么就是说明交叉了
        //end更新
        end = Math.min(end,intervals[i][1]);
        cnt++;
    }
    else{
        end = intervals[i][1];
    }
}

2 完整代码

• start指针没有用，但是写出

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length==1){
            return 0;
        }
        //按照区间起始位置排序
        Arrays.sort(intervals,(v1,v2)->v1[0]-v2[0]);
        //2 
        int start = intervals[0][0];
        int end = intervals[0][1];
        int cnt = 0;
        for(int i = 1;i<intervals.length;i++){
            if(end>intervals[i][0]){
                //当前end大于下一个区间的起点，那么就是说明交叉了
                //end更新
                end = Math.min(end,intervals[i][1]);
                cnt++;
            }else{
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        //cnt表示重叠的数目
        return cnt;
    }
}

戳气球问题

本质是计算无重叠区间问题，不过需要注意的是这里的区间相切，视作区间重叠，故代码的>又得换回>=拿最终的长度减去重叠的数目返回即可

1 完整代码

class Solution {
    public int findMinArrowShots(int[][] points) {
        //一样的套路，排序右边界
        if(points.length<=1){
            return 1;
        }
        Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
        //2 
        int start = points[0][0];
        int end = points[0][1];
        int cnt = 0;
        for(int i = 1;i<points.length;i++){
            if(end>=points[i][0]){
                //当前end大于等于下一个区间的起点，那么就是说明交叉了
                //end更新
                end = Math.min(end,points[i][1]);
                cnt++;
            }else{
                start = points[i][0];
                end = points[i][1];
            }
        }
        //cnt表示重叠的数目
        return points.length-cnt;
    }
}