Tham khảo đề bài:

Lời giải

Ta sắp xếp các đoạn ~[l_i, r_i]~ theo chiều tăng dần ~r_i~.

Để tối ưu nhất, ta tham lam chọn các phần tử từ phải sang trái và chưa được chọn trước đó của đoạn ~[l_i, r_i]~

Chứng minh:

Xét hai đoạn ~[l_i, r_i]~ và ~[l_j, r_j], (i < j)~ sau khi đã sắp xếp.

1) Trường hợp 1: ~[l_i, r_i]~ giao ~[l_j, r_j]~ ~(l_j \leq r_i)~:

• Nếu ta chọn các phần tử thuộc đoạn ~[l_j, r_i]~ thì thoả mãn được cùng lúc cả hai đoạn ~[l_i, r_i]~ và ~[l_j, r_j]~.

• Nếu ta chọn các phần tử thuộc nửa đoạn ~[l_i, l_j)~ thì chỉ thoả mãn được đoạn ~[l_i, r_i]~ mà không thoả mãn được đoạn ~[l_j, r_j]~.

• Suy ra ưu tiên chọn các phần tử bên phải của đoạn ~[l_i, r_i]~

2) Trường hợp 2: ~[l_i, r_i]~ không giao ~[l_j, r_j]~ (~r_i < l_j~).

• Trường hợp này, ta chọn phần tử nào trong đoạn ~[l_i, r_i]~ thì chỉ thoả mãn được đoạn ~[l_i, r_i]~.

Các bước thực hiện liên tục từ đoạn ~[l_1, r_1]~ tới đoạn ~[l_n, r_n]~ như sau:

• Nếu ~|Z \cap [l_i, r_i]| < c_i~ thì tham lam chọn các phần tử từ phải sang trái và chưa được chọn trước đó của đoạn ~[l_i, r_i]~.

• Nếu ~|Z \cap [l_i, r_i]| \geq c_i~ thì xét tiếp đoạn ~[l_{i+1}, r_{i+1}]~.

Các thao tác tìm ~|Z \cap [l_i, r_i]|~ và tham lam chọn phần tử có thể sử dụng Segment Tree và tìm kiếm nhị phân để giải quyết

Độ phức tạp: ~\mathcal{O}(nlog^2n)~. Code tham khảo