最大线段重合问题(用堆实现)

题目

给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间。
规定:
1)线段的开始和结束位置一定都是整数值
2)线段重合区域的长度必须>=1
返回线段最多重合区域中，包含了几条线段

认真分析题目，可以发现任何一个重合区域的左边界 必定是某个线段的左边界。

题解步骤：
1.把所有线段根据开始位置从小到大排好序
2.遍历所有线段，在小根堆中弹出所有<=开始位置的值
3.把线段的结束位置加入到小根堆中
4.小根堆中有几个数，就是这个线段的答案
5.返回所有线段中答案的最大值

所有线段根据开始位置从小大到大排好序这一步，我们不必自己写排序，可以用比较器，，

代码：

package com.harrison.class04;

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

/**
 * @author Harrison
 * @create 2022-03-02-21:17
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class Code06_MaxCover {
    // 1.把所有线段根据开始位置从小到大排好序
    // 2.遍历所有线段，在小根堆中弹出所有<=开始位置的值
    // 3.把线段的结束位置加入到小根堆中
    // 4.小根堆中有几个数，就是这个线段的答案

    //

    public static int maxCover1(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;
        for(double p=min+0.5; p<max; p+=1){
            int cur=0;
            for(int i=0; i<lines.length; i++){
                if(p>lines[i][0] && p<lines[i][1]){
                    cur++;
                }
            }
            cover=Math.max(cover,cur);
        }
        return cover;
    }

    public static int maxCover2(int[][] m){
        Line[] lines=new Line[m.length];
        for(int i=0; i<lines.length; i++){
            lines[i]=new Line(m[i][0],m[i][1]);
        }
        Arrays.sort(lines,new StartComparator());
        PriorityQueue<Integer> heap=new PriorityQueue<>();
        int max=0;
        for(int i=0; i<lines.length; i++){
            while(!heap.isEmpty() && heap.peek()<=lines[i].start){
                heap.poll();
            }
            heap.add(lines[i].end);
            max=Math.max(max,heap.size());
        }
        return max;
    }

    public static class Line{
        public int start;
        public int end;

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

    public static class StartComparator implements Comparator<Line>{
        public int compare(Line l1,Line l2){
            return l1.start-l2.start;
        }
    }

    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<ans.length; 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;
    }

    public static void main(String[] args) {
        int N=100;
        int L=0;
        int R=200;
        int testTimes=100000;
        System.out.println("test begin");
        for(int i=0; i<testTimes; i++){
            int[][] lines=generateLines(N,L,R);
            int ans1=maxCover1(lines);
            int ans2=maxCover2(lines);
            if(ans1!=ans2){
                System.out.println("oops");
            }
        }
        System.out.println("test finish");
    }
}