区间问题

0.整体思路： 区间按起始排序 + 比较

• 对于情况一，找到了覆盖区间。
• 对于情况二，两个区间可以合并，成一个大区间。
• 对于情况三，两个区间完全不相交。

  1.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 leetcode 56

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

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a0,a1)-> a0[0] - a1[0]);

        int idx = -1;
        int[][] res = new int[intervals.length][2];

        for(int[] interval : intervals){
            if(idx == -1 || interval[0] > res[idx][1]){
                res[++idx] = interval; // 情况三，两个区间完全不相交
            }else{
                // 情况二，两个区间可以合并，成一个大区间。
                res[idx][1] = Math.max(interval[1],res[idx][1]);
            }
        }

        return Arrays.copyOf(res, idx + 1);
    }
}

2.插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。 leetcode 57 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

1. 遍历intervals，首先将与被插入区间不相干的元素放在res
2. 将可以合并的元素与被插入区间合并后放入res

3. 将合并区间右侧的元素放入res

   public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][2];
        int idx = 0;
        // 遍历区间列表：
        // 首先将新区间左边且相离的区间加入结果集
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res[idx++] = intervals[i++];
        }
        // 接着判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，
        // 将最终合并后的新区间加入结果集
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        res[idx++] = newInterval;
        // 最后将新区间右边且相离的区间加入结果集
        while (i < intervals.length) {
            res[idx++] = intervals[i++];
        }
   
        return Arrays.copyOf(res, idx);
    }
   

3.删除被覆盖的区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。 leetcode 1288 只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 在完成所有删除操作后，请你返回列表中剩余区间的数目。

public int removeCoveredIntervals(int[][] intervals) {
        int count = intervals.length;

        //按起点升序 终点降序   排序
        Arrays.sort(intervals,(a0, a1) -> {
            if(a0[0] == a1[0]) return a1[1] - a0[1];
            return a0[0] - a1[0];
        });

        int[] sample = intervals[0];
        for(int i = 1; i < intervals.length; i++)
        {
            // 起点相同 或者 终点被覆盖
            if(intervals[i][0] == sample[0] ){
                count--;
            }else if( intervals[i][1] <= sample[1] ){
                count--;

            }

            //更新对照集
            else{
                sample = intervals[i];
            }
        }    

        return count;
    }

4.汇总区间

给定一个无重复元素的有序整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。 leetcode 228

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

双指针

• start 指针记录新区间左值
• end 指针记录右值

• 两个指针都从0开始，判断是否连续递增要判断 end+1 是否越界，找到区间后比较两个指针看要不要加箭头；

  public List<String> summaryRanges(int[] nums) {
        ArrayList<String> res = new ArrayList<>();
  
        int start = 0;
        int end = 0;
  
        while(end < nums.length){
            if(end < nums.length - 1 && nums[end + 1] == nums[end] + 1){
                end++;
            }
            else{
                if(start != end){
                    res.add(nums[start] + "->" + nums[end]);
                }else{
                    res.add(nums[start] + "");
                }
                end++;
                start = end;
            }
        }
  
        return res;
    }
  

  5.区间列表的交集

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。 返回这 两个区间列表的交集 。 leetcode 986

输入：firstList = [[0,2],[5,10],[13,23],[24,25]],
     secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

1. 两个数组已经排好序了，可以用两个索引指针i 和 j在firstList和secondList中游走，把交集找出来
2. 交集判断条件： low <= high

3. 指针i和j肯定要前进（递增）的

   public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int i = 0; // 维护两个数组的指针 
        int j = 0;
   
        int idx = 0;
   
        int[][] res = new int[firstList.length + secondList.length][2];
   
        while(i < firstList.length && j < secondList.length){
            // 求交集  
            int low = Math.max(firstList[i][0],secondList[j][0]);
            int high = Math.min(firstList[i][1],secondList[j][1]);
   
            if(low <= high){
                res[idx++] = new int[]{low,high};
            }
   
            // 移动指针 
            if(firstList[i][1] < secondList[j][1] ){
                i++;
            }else{
                j++;
            }
   
        }
   
        return Arrays.copyOfRange(res,0,idx);
    }
   

   6.俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里。 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封 leetcode 354

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]   
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

最长递增子序列问题

1. 先对宽度w进行升序排序，如果遇到w相同的情况，则按照高度h降序排序。

2. 之后把所有的h作为一个数组，在这个数组上计算 LIS 的长度就是答案。

   public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a1,a2) -> {
            if(a1[0] == a2[0]){
                return a2[1] - a1[1];
            }else{
                return a1[0] - a2[0];
            }
        });
   
        int n = envelopes.length;
        int[] dp = new int[n];
   
        //base case
        Arrays.fill(dp,1);
        int res = 1;
   
        for(int i = 0 ; i < n; i++){
            for(int j = 0; j < i ; j++){
                if(envelopes[i][1] > envelopes[j][1] ){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                res = Math.max(dp[i], res);
            }
        } 
        return res;
    }