牛客_线段重合问题

题目链接

首先得到线段的最大值和最小值

最大值和最小值按单位1等分，看每条线覆盖了多少，抓一下全局max

时间复杂度 O((max-min)*N)：

准备小根堆（之所以设置为堆，是因为要处理重复值，如果有序表的话，就无法接受重复值）

遍历每一个线段,得到其开始位置L和结束位置R，规则是：

0. 每个线段按开始位置L从小到大排序。

如果堆为空，线段结束位置R进入堆。

堆不为空，则遍历到线段L位置和堆顶元素(假设为M)比较，如果堆顶元素小于L，则结算一次堆中元素大小，记为size，然后弹出堆顶元素，直到堆顶元素小于L，然后把L加入

每次生成的size取最大值即为最大重合了几个线段

算法和数据结构笔记

程序员代码面试指南（第2版）

算法和数据结构基础班-左程云

极客时间-数据结构与算法之美-王争

算法(第四版)