题目描述

给定很多线段，每个线段都有两个数组[start, end]，表示线段开始位置和结束位置，左右都是闭区间。规定： 

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

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

• 题目要求：返回线段最多重合区域中，包含了几条线段

思路点拨

解法1（撮方法）

从最左端开始到最右端结束，对每个X.5位置都做一次统计，统计穿过当前X.5位置的线段条数count，最终返回所有count中的最大值。

---

解法2

过程阐述：

借助小根堆。先将所有线段按照起始位置排序（用C++内置的排序算法，时间复杂度O(NlogN)），然后按照顺序从小到大依次进行操作：先判断堆中是否存在小于等于当前线段起始点的值，然后将所有小于等于起始点的数pop出去，然后再将结束点push进来（小根堆里的数就是这么来的）。此时的count就等于小根堆中的元素个数。

原理阐释：

        解法2的思路是，对于每一次操作的线段，统计在它之前（起始点在它的起始点之前）的线段，共有多少条穿过它的起始点。最终返回最大值。

        由于是对一个已经根据起始点排序的线段序列进行操作，所以当进行到当前线段时，起始点在它起始点之前的线段都已经操作过了。

        那么为什么要将小于等于起始点的pop出去呢？由于整个过程都是按起始点从小到大来的，所以如果出现小根堆里的数小于等于当前起始点，就说明之前的那条线段已经完全“够不到”当前的这条线段了。而堆里大于当前起始点的数就表示之前的这条线段其结束位置“穿过”当前线段，所以统计堆中的数量就是当前为止穿过起始点的数量。由于自己本身也算，所以要先将当前线段的尾push到堆中再统计count。

        不用担心如果下一条线段如果与当前线段相交会“错过”。下一条线段不一定与这一条线段情况相同，即穿过当前起始点的线段不一定穿过下一个起始点。而下一条线段又统计穿过下一个起始点的count。所以它们之间并不会出现“重叠”或者是“遗漏”的情况。

        为什么起始点相同结束点顺序无所谓？因为是按照起始点的顺序来的，结束点一定大于起始点，如果几个起始点一样，那么它们的结束点都会被push进堆，并不会对结果产生什么影响。

我的题解

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

class segment
{
public:
	int start;
	int end;
	segment(int _start, int _end) :start(_start), end(_end) {}
};
class GetMostSegments
{
public:
	int getMost_1(const vector<segment> seg);
	int getMost_2(const vector<segment> seg);
	void test();
};

int main()
{
	GetMostSegments().test();
	return 0;
}

int GetMostSegments::getMost_1(const vector<segment> seg)
{
	int min_start = seg[0].start, max_end = seg[0].end;
	int cnt = 0;
	for (int i = 0; i < seg.size(); i++)
	{
		min_start = std::min(min_start, seg[i].start);
		max_end = std::max(max_end, seg[i].end);
	}
	for (double cur = min_start + 0.5; cur < max_end; cur++)
	{
		int tmp = 0;
		for (int i = 0; i < seg.size(); i++)
		{
			if (cur > seg[i].start && cur < seg[i].end)
				tmp++;
		}
		cnt = std::max(cnt, tmp);
	}
	return cnt;
}
int GetMostSegments::getMost_2(const vector<segment> seg)
{
	int cnt = 0;
	vector<segment> my_seg(seg); 
	//先按照起始点进行升序排序
	auto my_compare = [](const segment a, const segment b)
		{return a.start < b.start; };
	sort(my_seg.begin(), my_seg.end(), my_compare);
	//然后从前往后依次去找那个最大的cnt
	priority_queue<int, vector<int>, greater<int>> heap; //小根堆
	for (segment s : my_seg)
	{
		if (s.start == s.end) //起始点等于终止点，直接跳过
			continue;
		while (!heap.empty() && heap.top() <= s.start) //将已经越过的数排除出去
			heap.pop();
		heap.push(s.end);
		int cur_size = heap.size();
		cnt = std::max(cnt, cur_size);
	}
	return cnt;
}
void GetMostSegments::test()
{
	srand((size_t)time(0));
	int count = 100;
	for (int i = 0; i < count; i++)
	{
		vector<segment> seg;
		int segSize = rand() % 21 + 1; //防止出现空数组的情况
		for (int i = 0; i < segSize; i++)
		{
			int _start = rand() % 21;
			int _end = _start + rand() % 21;
			seg.push_back(segment(_start, _end));
		}
		int ans1 = GetMostSegments().getMost_1(seg), ans2 = GetMostSegments().getMost_2(seg);
		if (ans1 != ans2)
		{
			cout << "Error!" << endl;
			cout << "ans1: " << ans1 << "   " << "ans2: " << ans2 << endl;
			for (segment s : seg)
			{
				cout << s.start << "   " << s.end << endl;
			}
			return;
		}
	}
	cout << "run over!" << endl;
}