【Hello Algorithm】最大线段重合及加强堆

计算时间复杂度的技巧

一般来说 我们在刷算法的时候都要求C/C++语言在1到2s之内完成 java这种语言在2到4秒之内完成

而与之对应的指令条数就是 十的八次方 左右 不会超过一个数量级

所以说根据上面的结论 我们就能够反推题目所需要的时间复杂度

比如说一个数组的大小不超过 十的三次方 我们使用N平方的算法肯定能过

但是如果一个数组的大小不超过 十的六次方 我们就要考虑使用时间复杂度为N 或者是N*LogN的算法了

最大线段重合问题

题目描述如下

每一个线段都有start和end两个数据项，表示这条线段在X轴上从start位置开始到end位置结束。

给定一批线段，求所有重合区域中最多重合了几个线段，首尾相接的线段不算重合。

例如：线段[1,2]和线段[2.3]不重合。

线段[1,3]和线段[2,3]重合

我们下面先讲解题的具体方法 之后再说为什么要这么做

具体方法为：

1. 我们将所有的线段 按照起始位置从小到大的顺序排序
2. 我们设置一个小根堆
3. 从第一个线段开始遍历 首先看线段的起始位置值是多少
4. 将线段起始位置的值和小根堆里面的数进行比较并弹出所有小于等于该值的数字（没有或空就不弹）
5. 将第一个线段的结束位置的值加入到小根堆当中
6. 此时小根堆里面有几个数 就是该线段的答案
7. 之后重复步骤 3~6
8. 最后我们会得到一个最大值 该最大值就是我们的答案

下面是解释

我们求的最大值得含义是什么

因为我们再第一步将所有得线段按照起始位置从小到大的顺序排好序了

所以说 起始位置一定是在不断变大得（也有可能不变）

因此 我们只要记录每条线段末尾位置的值并且按照从小到大的顺序排序 就能够计算出以当前线段起点为起始位置的情况下穿过当前线段的线段有多少条

于是我们只要计算出每条线段起始位置穿过线段的最大条数之后比较取最大值就能够得到最后的答案了

为什么只要计算出每条线段起始位置穿过线段的最大条数就能够得出最后的答案

同学们可以在笔记上尝试画出任意条线段 找出它们的重合最多的区域之后观察

我们一定能发现 重合区域的起始位置一定是某条线段的起点

于是乎 我们只要计算出以每条线段为起始位置的重合区域最大值一定能够计算出最后的答案

起始位置相同 终止位置不同的线段排序会影响最终结果吗？

不会影响 因为这些线段的起始位置都相同 所以说不会影响小根堆里面的输出弹出 所以说不会影响到最终结果

题目地址及代码

此题可在牛客网上刷 线段重合

代码如下 起始只要理解了思路 代码并不难写

#include <iostream>
using namespace std;
#include <queue>
#include <vector>
#include <algorithm>
bool Less(const pair<int , int>& kv1 , const pair<int , int>& kv2)
{
    return kv1.first < kv2.first;
}
int main() 
{
    // num of section
    int count = 0;
    cin >> count;
    // receive section
    vector<pair<int , int>> v;
    int first = 0;
    int second = 0;
    while(count--)
    {
        cin >> first >> second;
        v.push_back(make_pair(first,second));
    }
    sort(v.begin() , v.end() , Less);
    int max = 0;
    priority_queue<int , vector<int> , greater<int>> pq;
    for (auto x: v)
    {
        while( (!pq.empty()) && pq.top() <= x.first)
        {
            pq.pop();
        }
        pq.push(x.second);
        max = max > pq.size()? max : pq.size();
    }
    cout << max << endl;
 }

加强堆

我们目前在C++中使用的一个 优先级队列 只是一个简单的堆模型

他给我们暴露出来的接口只能够让我们入堆和出堆 处理不了一些较为复杂的场景

比如说我们将堆中的一个元素值变大或者变小

• 第一 当前的堆无法支持我们上面说的变大变小操作
• 第二 修改之后堆无法自动恢复成一个新的堆

要想完成上面我们说的功能 我们的堆就必须要有一个反向索引表

什么是反向索引表

反向索引表是一张哈希表

我们的堆本质上是一个数组 但是我们每次加入一个新的元素之后我们就不能得知该元素的位置在数组的什么下标了

如果我们加上一个哈希表 通过这个哈希表 我们就能直接从这张表中找到元素对应的下标 那么这张哈希表就是我们堆对应的反向索引表

为什么堆不给我们提供反向索引表

因为在实际的引用场景中 我们使用堆并没有要用到反向索引表的场景 而如果我们添加了反向索引表 这实际上是一个非常耗费内存的行为

因此 在给我们使用的标准库中并没有添加反向索引表

如何做

我们前面说了 加强堆和堆之间只差了一个反向索引表

所以说我们只需要将堆的代码复制过来 并且给它的成员加上一个反向索引表

在需要改变下标的地方都修改下反向索引表即可

最后给加强堆加上一个接口 让其可以通过反向索引表修改堆内元素的大小（当然修改完也要记得调整位置）