贪心算法之线段覆盖问题

缘起

题意:

在一维空间中告诉你N条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度。

例如 [1,2] 和 [3,4] 覆盖了2的长度, 再加上[1,3] 则覆盖了4的长度，再加上[1,4]依然只覆盖了4的长度.

分析

贪心算法. 首先将起点升序排序. 然后遍历这些区间， 用j维护蔓延的最远的区间的下标. 如果考察的下一个区间i的begin都比j的end远，则更新j， 更新tot. 否则，考察i的begin, 它肯定是大于j的begin的（因为begin已经升序排过序了）. 考察i的end，如果end<=j的end的话，则i被j包裹住. 则不会增加tot也不会改变j, 否则，如果i的end>j的end的话, tot增加 ,j变化. 即描述的是下面3种情况

实现如下

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
#include "stdafx.h"
#include<iostream>
#include <algorithm>
#define LOCAL

using namespace std;

struct Segment
{
	int start, end; // 表示线段 [start, end]
	bool operator <(Segment s) {return start<s.start;} // 按照升序排序
}s[10];


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	for (int i=0;i<10;i++)scanf("%d", &s[i].start);
	for (int i=0;i<10;i++)scanf("%d", &s[i].end);

	sort(s,s+10);
	int tot = s[0].end-s[0].start, j = 0; // tot是最后的答案, j是当前蔓延的最远的
	for (int i = 1; i<10;i++) // 开始逐个考察后续9个区间
	{
		if (s[i].start>s[j].end) tot+=(s[j=i].end-s[i].start); // 情形1
		else
		{
			if (s[i].end<s[j].end) continue; // 情形2
			tot+=(s[i].end-s[j].end); // 情形3
			j = i;
		}
	}
	printf("%d\n",tot);
	return 0;
}
/*
测试数据
7 3 8 5 6 11 4 9 10 2
8 5 12 6 9 15 7 10 13 3
*/

不难知道最后算法复杂度是O(nlogn).