线段重合

[编程题]线段重合

热度指数：4892 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

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

输入描述:

第一行一个数N，表示有N条线段
接下来N行每行2个数，表示线段起始和终止位置

输出描述:

输出一个数，表示同一个位置最多重合多少条线段

示例1

输入

输出

备注:

算法知识视频讲解

查看答案及解析

Newyoung

思路：对线段按从小到大进行排序，建立一个小根堆
堆中存在的时线断的尾元素
每次循环，将堆中小于start的弹出，堆中剩余元素的个数就是通过该点的重合线段，
之后将end入堆
最大的重合线段数就是答案
原理：以start为比较器，那么通过重合线段就是删除完成后，离start最近的end
。其它元素都是大于这个end的，这样堆中的个数就是[start,end]的重合数

时间复杂度：O(N*logN)

//思路：对线段按从小到大进行排序，建立一个小根堆
//堆中存在的时线断的尾元素
//每次循环，将堆中小于start的弹出，堆中剩余元素的个数就是通过该点的重合线段，
//之后将end入堆
//最大的重合线段数就是答案
//原理：以start为比较器，那么通过重合线段就是删除完成后，离start最近的end
//。其它元素都是大于这个end的，这样堆中的个数就是[start,end]的重合数
//时间复杂度：O(N*logN)
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
struct Less
{
	bool operator()(const pair<int, int>& kv1, const pair<int, int>& kv2)
	{
		return kv1.first < kv2.first;
	}
};
template<class T>
class Greater
{
public:
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};
int main()
{
	//接受数据
	//int N = 0;
	//scanf("%d", &N);

	vector<pair<int, int>>v;//数据类型是键值对
	//int i = 0;
	/*while (i < N)
	{
		int first = 0;
		int second = 0;

		scanf("%d %d", &first, &second);
		if (first > second) std::swap(first, second);
		v.push_back(make_pair(first, second));
		++i;
	}*/
	v.push_back(make_pair(2, 3));
	v.push_back(make_pair(4, 6));
	v.push_back(make_pair(7, 8));
	v.push_back(make_pair(9, 10));
	v.push_back(make_pair(2, 3));
	v.push_back(make_pair(5, 7));
	v.push_back(make_pair(6, 10));
	v.push_back(make_pair(3, 8));

	sort(v.begin(), v.end(), Less());
	int MAX = 0;
	priority_queue<int, vector<int>, Greater<int>> pq;
	for (auto e : v)
	{
		//删除
		while ((!pq.empty()) &&
			(pq.top() <= e.first))
		{
			pq.pop();
		}
		//求重合线段
		pq.push(e.second);
		MAX = pq.size() > MAX ? pq.size() : MAX;
	}
	cout << MAX << endl;

	return 0;
}

发表于 2022-09-05 22:03:42 回复(0)

C++

牛客158448581号

#include <bits/stdc++.h>

using i64 = long long;

int main()
{   
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<std::pair<int, int>> lines(N);

    for (auto &[start, end] : lines) {
        std::cin >> start >> end;
    }

    std::sort(lines.begin(), lines.end());

    int ans = 1;
    std::priority_queue<int, std::vector<int>, std::greater<>> pq;

    for (const auto &[start, end] : lines) {
        pq.push(end);
        while (pq.top() <= start) {
            pq.pop();
        }
        ans = std::max(ans, static_cast<int>(pq.size()));
    }

    std::cout << ans << '\n';

    return 0;
}

发表于 2025-01-14 20:13:48 回复(0)

牛客310345383号

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

具体思路可以参考我的这篇博客

https://xuexitongxue.blog.csdn.net/article/details/132510876?spm=1001.2014.3001.5502

发表于 2023-08-28 22:14:48 回复(0)

C/C++

牛客530567606号

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n =0;
cin>>n;
vector<int>ad(100001,0);
int s = 0;
int e = 0;
while(n--)
{
cin>>s>>e;
if (s>e) swap(s,e);

for(int i = s-1; i<(e-1); ++i)
ad[i] += 1;
}
int ans = 0;
for(int i = 0; i < ad.size(); i++)
ans = max(ans,ad[i]);
cout<<ans;

return 0;
}

发表于 2022-05-19 22:05:02 回复(0)