Tóm tắt đề bài

Có \(N\) yêu cầu mượn sách, yêu cầu \(i\) là một đoạn thời gian \([a_i, b_i)\) (mượn lúc \(a_i\), trả lúc \(b_i\)). Bạn An cần chọn nhiều yêu cầu nhất sao cho các khoảng thời gian được chọn không giao nhau (không trùng thời gian sử dụng sách). In ra số lượng yêu cầu tối đa chọn được.

Phân tích

• \(N \le 10^4\), thời điểm \(a_i, b_i \le 32000\).
• Bài toán chính là chọn nhiều đoạn không giao nhau nhất (Interval Scheduling).

• Nhận xét quan trọng:

  • Nếu muốn chọn được nhiều đoạn nhất, ta nên ưu tiên đoạn có thời điểm kết thúc sớm hơn.
  • Trực giác: kết thúc sớm sẽ “chừa chỗ” cho nhiều yêu cầu tiếp theo.

• Lưu ý về “không giao nhau”:

  • Ví dụ mẫu chọn được \((1,3)\), \((4,7)\), \((7,9)\), tức là đoạn sau có thể bắt đầu đúng bằng lúc đoạn trước kết thúc.
  • Do đó điều kiện tương thích là \(a_{\text{mới}} \ge b_{\text{cuối}}\).

Hướng giải quyết

Nhận xét

Đây là bài toán tham lam kinh điển:

• Sắp xếp các yêu cầu theo \(b_i\) tăng dần (nếu bằng nhau có thể sắp theo \(a_i\) tăng dần cho ổn định).
• Duyệt theo thứ tự đó và chọn yêu cầu nếu nó bắt đầu không sớm hơn thời điểm kết thúc của yêu cầu cuối cùng đã chọn.

Chứng minh ý tưởng (tóm tắt):

• Giả sử ta có một nghiệm tối ưu. Nếu trong nghiệm đó, đoạn đầu tiên không phải là đoạn có \(b\) nhỏ nhất, ta có thể thay nó bằng đoạn có \(b\) nhỏ nhất mà vẫn không giảm số lượng đoạn chọn được (vì đoạn mới kết thúc sớm hơn hoặc bằng, không làm “mất chỗ” của các đoạn sau). Lặp lại lập luận cho các đoạn tiếp theo ⇒ tham lam là tối ưu.

Thuật toán

1. Đọc \(N\) và danh sách các cặp \((a_i, b_i)\).
2. Sắp xếp các yêu cầu theo:
   • Tăng dần theo \(b_i\).
   • Nếu \(b_i\) bằng nhau, tăng dần theo \(a_i\).
3. Khởi tạo:
   • lastEnd = -inf (hoặc \(0\) vì \(a_i > 0\)),
   • ans = 0.
4. Duyệt từng yêu cầu theo thứ tự đã sắp xếp:
   • Nếu \(a_i \ge lastEnd\):
     • Chọn yêu cầu này: ans++, cập nhật lastEnd = b_i.
5. In ans.

Độ phức tạp

• Thời gian: \(O(N \log N)\) do bước sắp xếp.
• Bộ nhớ: \(O(N)\) để lưu danh sách các yêu cầu.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pair<int,int>> seg(N);
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        seg[i] = {a, b};
    }

    // Sắp xếp theo thời điểm kết thúc tăng dần
    sort(seg.begin(), seg.end(), [](const auto &x, const auto &y) {
        if (x.second != y.second) return x.second < y.second; // b tăng
        return x.first < y.first; // nếu b bằng nhau, a tăng
    });

    int ans = 0;
    int lastEnd = 0; // vì 0 < a_i, ta có thể bắt đầu từ 0

    for (auto [a, b] : seg) {
        // Cho phép a == lastEnd (không giao nhau theo kiểu [a,b))
        if (a >= lastEnd) {
            ans++;
            lastEnd = b;
        }
    }

    cout << ans << "\n";
    return 0;
}