贪婪算法-区间选点问题

区间选点问题

问题描述

数轴上有 n 个闭区间 [ai, bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）

Input

第一行1个整数 N（N ≤ 100）
第 2~N+1 行，每行两个整数 a,b（a, b ≤ 100）

Output

一个整数，代表选点的数目

Sample

Input: 
2
1 5
4 6
Output: 
1

Input: 
3
1 3
2 5
4 6
Output: 
2

Limitation

Time limit		1000 ms
Memory limit	262144 kB

解题思路

按b的大小，将这些区间升序排序；当b相同时，按a降序。
排序完之后，将这些区间遍历，每次计数count增加时，证明这个区间与前面的区间没有重叠部分，因此可以把这个区间的b端作为接下来要判断的区间的判断点。
如果某区间与前一区间有重叠，那么一定有该区间的a端 ≤ 上一区间的b端且该区间的b端 ≥ 上一区间的b端。

如果第一字典不是b，而是a，按升序排列呢？

>>>第一字典为b
    (X)___________
(Y)________________________
                      (Z)_________
X和Y可共计1点, Z再算1点，总数共2点
-----------------------------------------
>>>第一字典为a
(Y)________________________
    (X)___________
                      (Z)_________
X的a在Y的b前面，但X的b也在Y前面。
情况一：
if条件不考虑X的b，则Y与X归类，标记点仍为Y的b
Z也会与Y归类。总数共计1点(Wrong Answer)
情况二：
if条件考虑X的b，Y不与X归类，计数+1，标记点变成X的b
X明显不能与Z归类，计数+1，标记Z的b，到尾了，计数+1
总数共计3点(Wrong Answer)

标记点若改成a端呢？
由于按a升序，按a端一定无法判断2个区间是否重叠！

源代码

#include <iostream>
#include <vector>
using namespace std;

/*两点 表示区间*/
struct range {
	int a, b;
	range(int _a, int _b) :a(_a), b(_b){}
};

int dotRange(vector<range> v) {
	//按b升序 按a降序
	for (int i = 0; i != v.size(); i++) {
		for (int j = 0; j != v.size() - 1 - i; j++) {
			if (v.at(j).b > v.at(j + 1).b)
				swap(v.at(j), v.at(j + 1));
			if (v.at(j).b == v.at(j + 1).b)
				if (v.at(j).a < v.at(j + 1).a)
					swap(v.at(j), v.at(j + 1));
		}
	}
	int dot = v.at(0).b;//排序后从头开始遍历 把第一个区间的末端作为判断点
	int count = 1;//计数
	for (int i = 1; i != v.size(); i++) {
		if (v.at(i).a <= dot && v.at(i).b >= dot) {//与本次标记区间有重叠 无需计数
			continue;
		}
		else {//到了没有重叠的区间 可计数
			count++;
			dot = v.at(i).b;//并以该区间的末端作为接下来的区间判断点
		}
	}
	return count;
}

int main() {
	int n;
	cin >> n;
	vector<range> v;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		range r(a, b);
		v.push_back(r);
	}

	cout << dotRange(v) << endl;

	return 0;
}