3925641_ac_63ms_832k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct node
{
	int start, end;

	bool operator < (const node & that)	const
	{
		if (this->start == that.start)
		{
			return this->end > that.end;
		}
		return this->start < that.start;
	}
}cow[25000];

vector <node> best;

int main()
{
	int i, n, t;

	scanf("%d%d", &n, &t);
	for (i = 0; i < n; i++)
	{
		scanf("%d%d", &cow[i].start, &cow[i].end);
	}
	sort(cow, cow + n);
	if (cow[0].start > 1)
	{
		puts("-1");
		return 0;
	}
	best.push_back(cow[0]);
	i = 1;
	while (i < n && best[best.size() - 1].end < t)
	{
		node tmp;
		tmp.start = tmp.end = 0;
		while (i < n && cow[i].start <= best[best.size() - 1].end + 1)
		{
			if (cow[i].end > tmp.end)
			{
				tmp = cow[i];
			}
			i++;
		}
		if (tmp.end == 0)
		{
			break;
		}
		best.push_back(tmp);
	}
	if (best[best.size() - 1].end >= t)
		printf("%d\n", best.size());
	else
		puts("-1");
	return 0;
}