ZOJ Problem Set - 3197
You, the best hacker in the world, want to download the books published on Google Book. After some investigation, you found that the address of each page consists of two parts. The first part is the page number, the second part is the signature which is unique for each page. To get the signature, you can send the query to the server. The query has one parameter, which indicates the page number. The server will return the signature of the required page, and it may also return the signature of some adjacent pages.
To minimize the bytes downloaded from the internet, and also make the server adminstrator hard to notice your "hack", you’d like to minimize the number of queries
Input
The input has multiple cases.
The first line of the input is a single integer T which is the number of test cases. Then T consecutive test cases follow. In each test case, the first line is a number N (1<=N<=5000), indicating the number of pages of the book. Then n lines follows. On the i-th line, there will be two integers ai and bi (ai<=i<=bi). They indicate that the query for the i-th page will return the signatures from page ai to page bi (inclusive)
Output
Results should be directed to standard output. The output of each test case should be a single integer, which is the minimum number of queries to get all the signatures.
Sample Input
23
1 1
2 2
3 3
3
1 1
1 3
3 3
Sample Output
31
// author: jfo()
////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int T, N;
set<int> P[5001];
int solve()
{
int request = 1;
int p = P[1].rbegin() + 1;
int i = 2;
while(p <= N) {
int m = 0;
for(; i <= p; i++) {
if(P[i].empty() || P[i].rbegin() < p)
continue;
if(m < P[i].rbegin())
m = P[i].rbegin();
}
p = m + 1;
request++;
}
return request;
}
int main()
{
cin >> T;
while(T– > 0) {
cin >> N;
for(int i = 0; i <= N; i++)
P[i].clear();
for(int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
P[a].insert(b);
}
cout << solve() << endl;
}
return 0;
}
闭区间覆盖问题（http://hi.baidu.com/tiaoshui/blog/item/a591b73531ab1a8ba71e1264.html）
问题描述：
设X1,X2,….Xn 是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?设计解此问题的有效算法，并证明算法的正确性。
编程任务：
对于给定的实直线上的n个点和闭区间的长度k，编程计算覆盖点集的最少区间数。
数据输入：
由文件input.txt给出输入数据。第一行有2 个正整数n和k，表示有n个点，且固定长度闭区间的长度为k。接下来的1 行中，有n个整数，表示n个点在实直线上的坐标（可能相同）。
结果输出:
将编程计算出的最少区间数输出到文件output.txt。
输入文件示例输出文件示例
input.txt output.txt
7 3 3
1 2 3 4 5 -2 6
算法：
对n个点坐标排序，从小到大，每次选取未被覆盖且坐标最小的点，以此点为起始位置，用长度K覆盖，直到所有点被覆盖。