算法：求最多线段重合次数

最近在业务开发时，需要求值机柜台资源分配的使用时间段重叠部分不能超过使用次数限制。 简化成算法问题，就是求多个开始-结束的线段的最大重叠时间次数。

举例： 求给定[1,3] [2,4] [4,7] [2,9]等线段求最大重合次数 答案是3次，1-3，2-4，2-9的重叠最大次数是3。

两种解题思路：

暴力破解

最多重叠的区域的结果的左端点leftx，数组其中的一个左端点。暴力遍历每一个左端点，落在最多数组时间端的就是最大重叠次数。

    /**
     * 最后重叠的线段的左节点一定是给定线段中其中一个线段的左节点
     * 因此求所有左节点，落在最多的线段中，就是最大重叠次数
     * O(N^2)
     * @param lines
     * @return
     */
    public static int maxLine1(int[][] lines){
        if(lines==null||lines.length==0) return 0;
        int max=1;
        for(int i=0;i<lines.length;i++){
            int left=lines[i][0];
            int t=0;
            for(int j=0;j<lines.length;j++){
                if(lines[j][0]<=left&&lines[j][1]>=left) t=t+1;
                max=Math.max(max,t);
            }
        }
        return max;
    }

小根堆

方案2：使用小根堆 满足条件的左节点一定是某个线段的左端点，那么通过该节点的线段一定左端点小于该结果leftx，右节点大于leftx。 通过小根堆的特性，留在堆的一定是大于左节点的端点。

1. 将所有线段按照左端点排序，减少遍历次数
2. 遍历每一个线段，对于每一个线段
3. 把右端点放入堆中，
4. 左节点与堆顶比较，如果堆顶的元素小于左端点全部弹出
5. 每次Max找最大重合次数作为答案

    public static int maxLine2(int[][] lines){
        if(lines==null||lines.length==0) return 0;
        Arrays.sort(lines,(a,b)->a[0]-b[0]);
        PriorityQueue<Integer> heap=new PriorityQueue<>();
        int max=1;
        for(int i=0;i<lines.length;i++){
            while (!heap.isEmpty()&&heap.peek()<=lines[i][0]) heap.poll();
            heap.add(lines[i][1]);
            max=Math.max(heap.size(),max);
        }
        return max;
    }