Sắp xếp chuỗi nhị phân để giá trị tối đa trong khoảng chỉ số C/C++

Cho chuỗi chỉ chứa 0 và 1, có M khoảng không giao nhau A, B (A <= B), cụ thể [A1,B1], [A2,B2], ..., [AM,BM]. Hai khoảng bất kỳ không chồng chéo – với i!=j, hoặc Ai

Nhiệm vụ: tìm hoán vị hợp lệ thỏa mãn đồng thời:

• Tổng số trong tất cả M khoảng cho trước là lớn nhất.
• Chuỗi lớn nhất về thứ tự từ điển (lexicographically maximum). Chuỗi 1100 > 1001.

Ví dụ

Input: 11100 3 3 4 5 5
Output: 00111
Đặt 1 ở vị trí 3,4 rồi 5 (không còn 1) -> 00111.

Input: 0000111 2 1 1 1 2
Output: 1110000
Đặt 1 ở vị trí 1,2 rồi 1 còn lại đặt vị trí 3 để lớn nhất về từ điển -> 1110000.