[算法]区间归并

问题分析

有的时候,会遇到给定一系列的区间,求交集or并集,或者合并的题.

这些题的解题方式比较通用个,做一个总结.

会用到集合和归并排序的相关知识.

两个区间的关系有六种,如果我们首先对区间按照区间左边界进行排序,那么就会编程3中关系:

A 包含  B ==> A[0] <= B[0] && A[1] >= B[1]

A 交集于  B  ==> A[0] <= B[0] || A[1]  >= B[1]

A 无交集 B ==>  A[1] < B[0]

解题套路

算法的题解法是:

首先对 区间集合进行排序.

将这些集合分为已归并 + 未归并

从已归并中取出最后一个  + 未归并的第一个进行计算:

根据以上的三种关系来处理已归并集合的最后一个区间:

A 包含  B ==> A[0] <= B[0] && A[1] >= B[1]   ==>  未归并 自动归并到已归并集合,不用处理

A 交集于  B  ==> A[0] <= B[0] || A[1]  >= B[1]  ==>  修改 已归并最后一个区间的右区间  为B[1]

A 无交集 B ==>  A[1] < B[0]   ==>   将B 区间添加到已归并区间中

示例

56. 合并区间

题解

class Solution {
    public int[][] merge(int[][] intervals) {

        /**
         * 首先做一个排序.按照做区间进行排序.将关系变为三种. 然后进行处理.
         * 区间的关系有三种:
         * 第一种是完全没有交集的.
         * 第二种是有交集,不是子集
         * 第三种是:有交集,是子集.
         */

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] here, int[] there) {
                if (here[0] != there[0]) {
                    return here[0] - there[0];
                } else {
                    return here[1] - there[1];
                }
            }
        });
        //左侧是最小的.
        List<int[]> result = new ArrayList<int[]>();
        result.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];
            int[] top = result.get(result.size() - 1);
            if (interval[0] <= top[1]) {
                //有交集
                if (interval[1] >= top[1]) {
                    top[1] = interval[1];
                }
                //子集忽略
            } else {
                //无交集,之间的结束
                result.add(interval);
            }
        }
  

        return result.toArray(new int[result.size()][]);
    }

}

986. 区间列表的交集

题解:

class Solution {
   public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {

        /**
         * 求出交集的实现方式.首先将所有的元素进行排序,然后不断的求并集,然后依次用后面的和前面的取交集
         */

        /**
         * 这个题中,内部不相交,所以只需要和另外一个数组中的区间取交集就好了.如果一旦取过以后,就没有交集了.类似于归并排序.
         */
        int firstRank = 0, secondRank = 0;
        List<int[]> result = new ArrayList<>();
        while (firstRank < firstList.length && secondRank < secondList.length) {
            int low = Math.max(firstList[firstRank][0], secondList[secondRank][0]);
            int high = Math.min(firstList[firstRank][1], secondList[secondRank][1]);

            if (low <= high) {
                result.add(new int[]{low, high});
            }

            if (firstList[firstRank][1] == high) {
                firstRank++;
            }
            if (secondList[secondRank][1] == high) {
                secondRank++;
            }
        }
        return result.toArray(new int[0][2]);
    }
}

57. 插入区间

 题解:

class Solution {
   public int[][] insert(int[][] intervals, int[] newInterval) {

        List<int[]> result = new ArrayList<>();
        boolean newAccepted = false;
        int left = 0;
　　　　//这里套用了 归并排序模板
        while (left < intervals.length || !newAccepted) {
            int[] interval = null;
            if (newAccepted) {
                interval = intervals[left++];
            } else if (left >= intervals.length) {
                 interval = newInterval;
                newAccepted = true;
            } else if (intervals[left][0] < newInterval[0] || (intervals[left][0] == newInterval[0] && intervals[left][1] < newInterval[1])) {
                interval = intervals[left++];
            } else {
                interval = newInterval;
                newAccepted = true;
            }

            if (result.size() == 0) {
                result.add(new int[]{interval[0], interval[1]});
            } else {
                int[] top = result.get(result.size() - 1);
                if (interval[0] <= top[1]) {
                    //有交集
                    if (interval[1] > top[1]) {
                        //交集集
                        top[1] = interval[1];
                    }
                    //子集不用管
                } else {
                    //没有交集
                    result.add(new int[]{interval[0], interval[1]});
                }
            }
        }

        return result.toArray(new int[0][]);
    }

}