11776 - Oh Your Royal Greediness!(最大重疊區間)

Problem F
Oh Your Royal Greediness!

Input: Standard Input

Output: Standard Output

Once upon a time there lived a greedy landlord in a not far far away country. The landlord used to employ armed enforcers to ensure tax collection from his subjects. All his subjects were farmers and they depended solely on their crops to pay tax. In any single year, an individual farmer had crops in his field during a single continuous time interval. During this interval, an enforcer from the landlord was present in the farmer's field so that he could make sure to take away most of the produced crops to the landlord's burn. An enforcer could take care of at most one farmer at a time.

Now, in a glorious lazy morning, the landlord realized that a lot of his subjects were having intersecting production intervals. As he was determined to take the lion's share of crops from all the farmers, he sat down to determine the minimum number of enforcers he needed to ensure that no farmer remained unguarded while having crops in his field.

Oh your royal greediness! Don't you realize he who is greedy is always in want?

Input

There will be multiple test cases in the input file. A test case starts with an integer N (0<=N<=1000), denoting the number of farmers. Each of the following N lines contains 2 integers S & E (0<=S<=E<=31536000), the starting & ending time respectively of the production interval of a farmer. Note that time is given in seconds from the start of the year.

The end of input will be denoted by a case with N = -1. This case should not be processed.

Output

For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the minimum number of enforcers required.

Sample Input Output for Sample Input

4

2 6

8 12

4 9

11 14

2

1 2

2 3

-1

Case 1: 2

Case 2: 2

題意：n個農民，看守每次相同時間只能看一個農民，問最少需要幾個看守保證每個農民都能看守到。

思路：先排序，然後按右區間選，然後看覆蓋到了幾個區間，每次維護最大值即可。

代碼：

#include 
#include 
#include 
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 1005;
	
int n;
struct Q {
	int s, e;
} q[N];

void init() {
	for (int i = 0; i < n; i++)
		scanf("%d%d", &q[i].s, &q[i].e);
}

bool cmp(Q a, Q b) {
	return a.e < b.e;
}

int solve() {
	int ans = 0, v = -1;
	sort(q, q + n, cmp);
	for (int i = 0; i < n; i++) {
		if (v == q[i].e) continue;
		v = q[i].e; int count = 1;
		for (int j = i + 1; j < n; j++) {
			if (q[j].s <= v) count++;
		}
		ans = max(count, ans);
	}
	return ans;
}

int main() {
	int cas = 0;
	while (~scanf("%d", &n) && n != -1) {
		init();
		printf("Case %d: %d\n", ++cas, solve());
	}
	return 0;
}