【Hello Algorithm】最大线段重合及加强堆-Toy模板网

这篇具有很好参考价值的文章主要介绍了【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]重合

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

具体方法为：

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

下面是解释

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

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

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

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

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

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

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

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

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

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

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

题目地址及代码

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

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

#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;
 }