摘要：贪心，问题分解。

因为行列无关，所以这个二维问题可以分解成两个一维问题。

优先队列实现：类似区间点覆盖的问题，先按照左端点排序，相同然后在按右端点排序（灵活性小的优先选）。最优的选法，当然是要使选的这个点经过的区间越少越好，那么就选最左边的点，因为选右边可能多经过区间，一定不比选最左边的更优。选完之后，就要把选过的点last忽略，并且把包含这个点的区间做修改，这个修改是动态的，可用优先队列

71ms

#include
      
       using namespace std;const int maxn = 5003;struct seg{    int l,r,id;    seg(int L,int R) { l = L; r = R; }    seg(){}    bool operator < (const seg& rhs) const {        return l > rhs.l || ( l == rhs.l && r > rhs.r);    }};seg dim[2][maxn];int rooks[maxn][2];priority_queue
       
         q;bool solve(int n,int d){    for(int i = 0; i < n; i++){       q.push(dim[d][i]);    }    int last = 0;    int id = 0;    while(q.size()){        seg cur = q.top(); q.pop();        if(cur.l>cur.r) return false;        if(cur.l<=last) {            cur.l = last + 1; q.push(cur);        }else {            last = cur.l;            rooks[cur.id][d] = cur.l;        }    }    return true;}int main(){    //freopen("in.txt","r",stdin);    int n;    seg *R = dim[0], *C = dim[1];    for(int i = 0; i < maxn; i++) dim[0][i].id = dim[1][i].id = i;    while(~scanf("%d",&n)&&n){        for(int i = 0; i < n; i++){            scanf("%d%d%d%d",&R[i].l,&C[i].l,&R[i].r,&C[i].r);        }        if(solve(n,0)&&solve(n,1)){             for(int i = 0; i < n; i++){            printf("%d %d\n",rooks[i][0],rooks[i][1]);            }        }else puts("IMPOSSIBLE");    }    return 0;}
       
      

另外一种贪心，直接按照右端点排序，优先处理右端点最小的区间，因为它的灵活性最小。从左往右边选点，使当前点尽量避免经过没有选点的区间。

这样做的效率要更高

11ms

#include
      
       using namespace std;const int maxn = 5003;struct seg{    int l,r,id;    bool operator < (const seg& rhs) const {        return r < rhs.r ;    }};seg dim[2][maxn];int rooks[maxn][2];bool solve(int n,int d){    int last = -1;    seg *Dim = dim[d];    bool vis[n+1];    memset(vis,0,sizeof(vis));    sort(Dim,Dim+n);    for(int i = 0; i < n; i++){        int j;        for(j = Dim[i].l; j <= Dim[i].r; j++) if(!vis[j]) {                rooks[Dim[i].id][d] = j; vis[j] = true; break;        }        if(j>Dim[i].r) return false;    }    return true;}int main(){    int n;    seg *R = dim[0], *C = dim[1];    while(~scanf("%d",&n)&&n){        for(int i = 0; i < n; i++){            scanf("%d%d%d%d",&R[i].l,&C[i].l,&R[i].r,&C[i].r);            R[i].id = C[i].id = i;        }        if(solve(n,0)&&solve(n,1)){             for(int i = 0; i < n; i++){            printf("%d %d\n",rooks[i][0],rooks[i][1]);            }        }else puts("IMPOSSIBLE");    }    return 0;}