Cho 1 bàn cờ n*n (n<=3000). Phải đặt n con xe vào bàn cờ sao cho:
_ Không có 2 con xe nào ăn được nhau
_ Con xe thứ i phải được đặt trong hcn có góc trái trên là (Li, Ui) và góc phải dưới là (Ri, Di). Các hcn có thể giao nhau.
Hình như bài này là cặp ghép ?

He toa do :
-->y
|
x
Gia su toa do moi hcn la (x1,y1), (x2,y2) (x la toa do doc, y la toa do ngang, x1 <x2, y1<y2)
Dau tien ta sort theo y2, sau do dat cac quan co lan luot vao cac cot nhu sau:
Di tu y1 --> y2, o nao trong thi dat vao.
Neu khong dat duoc --> khong co cach sap
Ta lai lam nhu vay voi x2, tuc la sort theo x2 ... roi dat lan luot vao hang.

Hinh nhu voi test hiem thi van khong chay duoc.

Eo. Mình ghét nhất mấy bài kiểu này. Khó.