贪婪算法-区间覆盖问题

区间覆盖问题

问题描述

数轴上有 n (1 ≤ n ≤ 25000) 个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t] ( 1 ≤ t ≤ 1,000,000)。
覆盖整点，即[1,2]+[3,4]可以覆盖[1,4]。
不可能办到输出-1

Input

第一行：N 和 T
第二行至 N+1 行: 每一行一个闭区间。

Output

选择的区间的数目，不可能办到输出-1

Sample

Input: 
3 10
1 7
3 6
6 10
Output: 
2

Limitation

Time limit		1000 ms
Memory limit	65536 kB

解题思路

这道题WA了好多次，主要是整点覆盖比较坑，是要在录入时就进行始端-1或者末端+1，还是在if条件判断的时候考虑整点，容易出错，可能会多考虑了区间比如[1, 2]和[4, 5] (2往后延长到3, 4往前延长到3)。还有录入的时候我进行了裁剪，我怕[-2, 1]裁剪成[1, 1]会影响对[2, 3]的判断，就选择了在if处判断整点，而没有选择延长区间。

首先对区间a升序，a相同时按b降序，保证每次能选到的区间最长。每次标记一个区间的起点begin和终点end，再从接下来的区间中选取起点落在[begin, end+1]范围内的，可行就选取最长的，然后更新起点begin和终点end，计数 + 1，如此循环，直到遇到目标终点t。

源代码

#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

/*区间 [a, b] */
struct range {
	int a, b;
	range(int _a, int _b) :a(_a), b(_b) {}
	bool operator < (const range r)const {
		if (a == r.a)
			return b > r.b;
		return a < r.a;
	}
};

int rangeCover(vector<range> v, int t) {
	//按a升序 按b降序
	sort(v.begin(), v.end());

	if (v.at(0).a > 1)//起始不是 1，一定不能办到
		return -1;
	//标记当前选取区间的起点，终点
	int begin = 1, end = v.at(0).b, pos = 0, count = 1;

	while (end != t) {
		int temp = 0;
		begin = end + 1;//下一个标记的起始点为本次标记终点+1
		for (int i = pos; i < v.size(); i++) {
			if (v.at(i).a > begin) {//遇到了第一个起始点 > 标记起始点的
				pos = i;
				break;
			}
			else if (v.at(i).a <= begin && v.at(i).b >= end) {//可选区间
				temp = i;//记录当前标号
				end = v.at(i).b;//更新标记末端
			}
		}
		if (begin > end) {//标记了下一个区间的起始点 但没有找到此区间
			return -1;
			break;
		}
		else {//这个标记的区间可行
			pos = temp + 1;//从那个标记的标号开始 进行下一次循环
			count++;//计数+1
		}
	}

	return count;
}

int main() {
	int n, t;
	scanf_s("%d%d", &n, &t);
	vector<range> v;
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf_s("%d%d", &a, &b);
		if ((a >= 1 && a <= t) || (b >= 1 && b <= t)) {//先对输入进行裁剪
			if (a < 1)//合法区间 但 a < 1，可令 a = 1
				a = 1;
			range r(a, b);
			v.push_back(r);
		}
	}

	int res = rangeCover(v, t);
	printf("%d\n", res);

	return 0;
}