算法 *-* 区间问题

总结

1.画图,画图,画图。直观观察规律

2.排序,排序,排序。按照起点/终点排序,或者混合排序。

        int[][] points = new int[][]{{1,2},{1,4},{10,18},{7,11},{3,6}};

        // 按照起点升序排列;起点相同时,终点按照降序排列
        Arrays.sort(points, new Comparator<int[]>(){
            @Override
            public int compare(int[] a,int[] b){
                if(a[0] == b[0]){
                    return b[1] - a[1];
                }
                return a[0] - b[0];
            }
        });
        
        //排序后,points变成 [[1,4],[1,2],[3,6],[7,11],[10,18]]

3.什么情况下要“起点升序排序,(起点相同时)终点降序排序?”

当你需要“消除”重叠区间时,“起点升序排序,(起点相同时)终点升序排序”。详看文章

当你需要“覆盖”区间时,“起点升序排序,(起点相同时)终点降序排序”。详看文章

4.通解通法来讲,什么时候区间序列要按照“起点排序”?什么时候按照“终点排序”? -- 按道理说,两种排序都可以,可以在实际问题中进行尝试。

区间相关题目

一文秒杀所有区间相关问题

贪心算法之区间调度问题

原文地址:https://www.cnblogs.com/frankcui/p/14209558.html