堆相关例子-最大线段重合问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了堆相关例子-最大线段重合问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述

给定很多线段，每个线段都有两个数[start, end]，

表示线段开始位置和结束位置，左右都是闭区间

规定：

1）线段的开始和结束位置一定都是整数值

2）线段重合区域的长度必须>=1

返回线段最多重合区域中，包含了几条线段

例如：[3,10],[3,4],[5,9],[7,13],[9,10]返回3

暴力方式解题

思路

先得到线段最小点和最大点，这是所有线段在x轴上的范围在该范围上，取小数点如0.5进行查看，即查看每个0.5位置，有没有线段包含该点，记录多少条线段 max 用一个变量cover保存所有点中最多覆盖的线段条数最后得到的cover就是重合区域最多的线段数目

图例

堆相关例子-最大线段重合问题,算法,算法,java,数据结构

利用小根堆解题

思路

1.将开始点排序后，遍历该数组

2.将堆中所有 <= 当前线段的开始点的数弹出

3.将该点的结束点加入到堆中

4.记录过程中堆的历史最大长度

5.遍历结束后该长度就是其重合最多线段的个数

图例

待排序数组，且以按开始点排序

[3,10],[3,4],[5,9],[7,13],[9,10]

1. 遍历到[3,10]时

堆相关例子-最大线段重合问题,算法,算法,java,数据结构

2. 遍历到[3,4]时

堆相关例子-最大线段重合问题,算法,算法,java,数据结构

3. 遍历到[5,9]时

堆相关例子-最大线段重合问题,算法,算法,java,数据结构

4.遍历到[7,13]时

堆相关例子-最大线段重合问题,算法,算法,java,数据结构

5.遍历到[9,10]时

堆相关例子-最大线段重合问题,算法,算法,java,数据结构文章来源地址https://www.toymoban.com/news/detail-706676.html

code

public static int coverMax(int [][] lines){
        if(lines.length < 2)
            return 0;
        Arrays.sort(lines, (a, b) -> (a[0] - b[0]));
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int max = 0;
        for (int [] line : lines){
            while (!minHeap.isEmpty() && minHeap.peek() <= line[0]){
                minHeap.poll();
            }
            minHeap.add(line[1]);
            max = Math.max(max,minHeap.size());
        }
        return max;
}

到了这里，关于堆相关例子-最大线段重合问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！