题意
在n*n的棋盘上的n个指定区间上各放1个'车’ ， 使他们相互不攻击（不在同行或同列），输出一种可能的方法。
分析
每行每列都必须放车，把行列分开看，若行和列同时有解，则问题有解。这样就变成了n个区间选n个点的贪心问题。对每个点x选择包含它的最优未使用的区间，这个最优区间就是右界最小的区间。因为在给k找最优区间时，1~k-1的最优区间都已经找好了。
#include <bits/stdc++.h>
using namespace std;
const int N = ;
int xl[N], yl[N], xr[N], yr[N], x[N], y[N], n; bool solve(int a[], int l[], int r[]) {
int cur, mr;
//mr为包含k的区间最小右界，cur为放k的最优区间
memset(a, -, sizeof(int)*n);
for(int k = ; k <= n; ++k)
{
cur = -, mr = N;
for(int i = ; i < n; ++i)
if(a[i] < && l[i] <= k && r[i] < mr)
mr = r[cur = i];
if(cur < || k > mr) return ;
a[cur] = k;
}
return ;
} int main()
{
while(~scanf("%d", &n), n) {
for(int i = ; i < n; ++i)
scanf("%d%d%d%d", &xl[i], &yl[i], &xr[i], &yr[i]); if(solve(x, xl, xr) && solve(y, yl, yr))
for(int i = ; i < n; ++i)
printf("%d %d\n", x[i], y[i]);
else puts("IMPOSSIBLE");
}
return ;
}