poj 2376 Cleaning Shifts 贪心

缘起

日常浪费生命 poj 2376 Cleaning Shifts

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给定N个小区间以及区间起点终点，求能用它们覆盖区间[1,T]的最小组合。办不到输出-1

【输入】
区间个数N和T，(1 <= N <= 25000)，(1 <= T <= 1000000)

【输出】
最少需要区间的个数或者-1

【样例输入】
3 10
1 7
3 6
6 10

【样例输出】
2

【限制】
1s

贪心， 将所有区间按照起点升序排序. 则每次只需要找属于当前区间内的并且蔓延最远的区间即可. 例如当前区间是[1,5], 怎么找下一个区间呢? 或者说下一个区间怎么确定呢? 例如起点在[1,5]范围内的区间有[2,4],[2,8],[3,7],[4,6]（注意，这四个区间是起点排序了的，终点未必有序）

则找到终点最远的那个. 也就是[2,8]作为下一个区间. 如果没有任意一个区间的起点在[1,5]内，则算法终止，输出-1. 所以说——贪心之所以快，完全是因为贪心是一直向前的算法!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,t;

struct Interval
{
	int s,e;
	bool operator<(Interval b)
	{
		return s<b.s; // 按照起点升序排序
	}
}is[25005];

int sz()
{
	if (is[0].s!=1)
	{
		return -1;
	}
	int ans = 1, j=is[0].e, i=0; // j是目前最远蔓延到了多远, is[i]就是这个蔓延最远的区间
	while(i<n&&j<t) // 只要还没蔓延完,并且还有区间可供选择
	{
		int _maxi=i,_max=is[i].e,k=i;
		while(k<n&&is[k].s<=is[i].e+1) // 提醒一下，区间可以是断的，比如[1,3] [4,7] 只要后一个start<=前一个end+1就行
		{
			if (is[k].e>_max)
			{
				_maxi = k;
				_max = is[k].e;
			}
			k++;
		} // 最后 is[_maxi] 就是新的蔓延区间
		if (_max<=is[i].e) // 如果没有实质性的蔓延
		{
			return -1;
		}
		i = _maxi;
		j = _max; // 更新当前蔓延最远的区间
		ans++;
	}
	if (j<t) // 如果最后还是小于t,也就是还未能全覆盖
	{
		return -1;
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &t);
	for (int i = 0; i<n;i++)
	{
		scanf("%d%d", &is[i].s, &is[i].e);
	}
	sort(is, is+n);
	printf("%d\n",sz());
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 280kB
Length 1022
Lang C++
Submitted 2019-08-24 07:55:57
Shared
RemoteRunId 20794052