最大线段重合问题（堆实现的方式）

package class07;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 最多线段重合问题（堆实现的方式）
 * <p>
 * 给定很多线段，每个线段都有两个数[start, end]，
 * 表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须>=1
 * 返回线段最多重合区域中，包含了几条线段
 */
public class Code01_CoverMax {

    //获取重合的线段最多有多少条。
    //效率低的方法。机器笔试时可能可以通过，但是面试时这种方法不通过，没分。
    private static int CoverMax1(int[][] lines) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < lines.length; i++) {
            min = Math.min(min, lines[i][0]);//获取线段的开始值
            max = Math.max(max, lines[i][1]);//获取线段的结束值
        }
        int cover = 0;
        //定义一个不是整数的数，把经过此数的线段的条数，汇总累加到cover上。
        for (double p = min + 0.5; p < max; p++) {
            int cur = 0;
            for (int i = 0; i < lines.length; i++) {
                //当一条线段的开始值小于p，并且结束值大于p时，将cur++。
                //表示经过p这个小数的线段，有cur条。
                if (lines[i][0] < p && lines[i][1] > p) {
                    cur++;
                }
            }
            //对于此次循环的小数p，当所有线段都走了一遍时，看看时当前的cur大，还是之前的线段累加和cover大。
            //获取一个较大的值，作为cover。即更新"重合的线段最多的条数"。
            cover = Math.max(cover, cur);
            //此时p要++了，即换下一个小数p，看看经过p的线段共有多少条。
        }
        return cover;
    }

    //用堆实现的方式
    public static int CoverMax2(int[][] m) {
        //先定义一个Line类型，再定义一个Line类型的数组。
        Line[] lines = new Line[m.length];
        for (int i = 0; i < m.length; i++) {
            lines[i] = new Line(m[i][0], m[i][1]);//给lines数组的每一个元素赋值。
        }
        Arrays.sort(lines, new StartComparator());//使用自定义比较器，给lines数组排序。

        //定义优先级队列，使用默认的小根堆，即最小值在最上边。将每次循环的线段的结束值加入进去。
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int max = 0;
        for (int i = 0; i < lines.length; i++) {
            //当heap不为空，并且heap的栈顶，即最小值小于等于，当前循环中的线段的开始值时。
            while (!heap.isEmpty() && heap.peek() <= lines[i].start) {
                heap.poll();//弹出heap的栈顶，即最小值。
            }
            heap.add(lines[i].end);//往heap中添加当前循环的线段的结束值。
            max = Math.max(max, heap.size());//更新heap的个数。把较大的数赋值给max。
        }
        return max;//返回最大的heap的个数，就是结果。
    }

    //和CoverMax2()的过程一样，只是CoverMax3()的代码更短，没有使用类定义的方式。
    public static int CoverMax3(int[][] m) {
        //m是二维数组，可以因为m内部是一个一个的一维数组。
        //每一个一维数组就是一个对象，也就是线段。
        //下边的code，就是根据每一个线段的开始值升序排序。
        Arrays.sort(m, (a, b) -> (a[0] - b[0]));
        //定义小根堆。
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int max = 0;
        for (int[] line : m) {
            if (!heap.isEmpty() && heap.peek() <= line[0]) {//"line[0]"就是每一个线段的开始值
                heap.poll();
            }
            heap.add(line[1]);//"line[1]"就是每一个线段的结束值
            max = Math.max(max, heap.size());
        }
        return max;
    }


    public static class Line {
        int start;
        int end;

        public Line(int s, int e) {
            start = s;
            end = e;
        }
    }

    /**
     * for test
     * 生成随机的线段，即线段的开始数值，和结尾数值都是随机的，并且开头小于结尾。
     *
     * @param N 要生成多少条随机线段
     * @param L 当前生成的线段的开头数值
     * @param R 当前生成的线段的结尾数值
     * @return 生成的随机的N条记录。二维数组类型。
     */
    public static int[][] generateLines(int N, int L, int R) {
        int size = (int) (Math.random() * N) + 1;
        int[][] ans = new int[size][2];
        for (int i = 0; i < size; i++) {
            int a = L + (int) (Math.random() * (R - L + 1));
            int b = L + (int) (Math.random() * (R - L + 1));
            if (a == b) {
                b = a + 1;
            }
            ans[i][0] = Math.min(a, b);
            ans[i][1] = Math.max(a, b);
        }
        return ans;
    }

    //自定义比较器
    //按照每个元素的开始值start升序。
    private static class StartComparator implements Comparator<Line> {
        @Override
        public int compare(Line o1, Line o2) {
            return o1.start - o2.start;
        }
    }


    public static void main(String[] args) {
        Line line1 = new Line(2, 8);
        Line line2 = new Line(6, 8);
        Line line3 = new Line(6, 9);
        Line line4 = new Line(4, 5);
        Line line5 = new Line(2, 6);
        Line line6 = new Line(3, 7);

        //简单测试，定义一个优先级队列，在构造方法中传入自定义比较器。
        //那么在heap添加line元素的数据，就是按照line的开始值start，进行升序排序并保存的。
        //当然，在heap.poll()的时候，获取line元素，就是start最小的line元素。
        PriorityQueue<Line> heap = new PriorityQueue<>(new StartComparator());
        heap.add(line1);
        heap.add(line2);
        heap.add(line3);
        heap.add(line4);
        heap.add(line5);
        heap.add(line6);
        while (!heap.isEmpty()) {
            Line poll = heap.poll();
            System.out.println(poll.start + ", " + poll.end);
        }

        System.out.println("======================");
        int testTimes = 1;
        int N = 100;
        int L = 0;
        int R = 100;
        System.out.println("test start!");
        for (int i = 0; i < testTimes; i++) {
            int[][] lines = generateLines(N, L, R);
            System.out.println("lines = " + Arrays.deepToString(lines));
            //lines = [[72, 82], [51, 75], [0, 83], [9, 97], [30, 90], [45, 58], [26, 58], [48, 98], [57, 86], [30, 62], [69, 84], [16, 66], [20, 78], [65, 95], [6, 37], [42, 87], [22, 89], [11, 14], [55, 71]]
            int ans1 = CoverMax1(lines);
            int ans2 = CoverMax2(lines);
            int ans3 = CoverMax3(lines);
            System.out.println("ans1 = " + ans1);
            System.out.println("ans2 = " + ans2);
            System.out.println("ans3 = " + ans3);
            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test end!");
    }

}