uva 11776 - Oh Your Royal Greediness!(暴力）

題目鏈接：11776 - Oh Your Royal Greediness!

題目大意：有n農民，給出每個農民的工作的起始時間和終止時間。然後每個農民在工作的時候都必須有一個監工，問最少需要幾個監工。

解題思路：一開始以為是區間選點問題，後來WA了。然後直接暴力就過了。以每個農民的結束時間為標准，若其他人的起始時間小於這個標准，並且終止時間大於這個標准，監工數就要加+1，然後從中選出最大值。

#include 
#include 
#include 

using namespace std;

const int N = 1005;
int n;
struct state {
	int x, y;
}s[N];

bool cmp(const state& a, const state& b) {
	return a.x < b.x;
}

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

int solve() {
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int cnt = 0;
		for (int j = 0; j < n; j++) {
			if (s[j].x > s[i].y) break;
		    if (s[j].x <= s[i].y && s[j].y >= s[i].y) cnt++;
		}
		ans = max(ans, cnt);
	}
	return ans;
}

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