Hiểu bài toán

Bài toán yêu cầu tìm số lượng lớn nhất các bộ phim có thể xem được trong một ngày, với điều kiện không có hai bộ phim nào được xem chồng lấn thời gian. Mỗi bộ phim có thời gian bắt đầu (a) và kết thúc (b). Ta cần chọn một tập hợp con các bộ phim sao cho khoảng thời gian của chúng không giao nhau và số lượng là lớn nhất.

Các cách tiếp cận

Cách Sắp xếp theo thời gian bắt đầu (Greedy)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> movies(n);
    for (int i = 0; i < n; i++) {
        cin >> movies[i].first >> movies[i].second;
    }

    // Sắp xếp theo thời gian bắt đầu
    sort(movies.begin(), movies.end());

    int cnt = 0;
    int lastEnd = -1e9;

    for (auto &m : movies) {
        // Nếu bắt đầu sau hoặc bằng thời điểm phim trước kết thúc
        if (m.first >= lastEnd) {
            cnt++;
            lastEnd = m.second;
        }
    }

    cout << cnt;
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Cách tiếp cận này sắp xếp các bộ phim theo thời gian bắt đầu. Sau đó, ta duyệt qua danh sách và chọn bộ phim đầu tiên. Với các bộ phim tiếp theo, ta chỉ chọn nó nếu thời gian bắt đầu của nó lớn hơn hoặc bằng thời gian kết thúc của bộ phim vừa chọn. Tuy nhiên, cách này KHÔNG đảm bảo tối ưu vì việc chọn bộ phim bắt đầu sớm nhất có thể khiến ta không thể xem được nhiều phim sau đó (ví dụ: phim [1, 100] và [2, 3], [3, 4]...).

Cách Sắp xếp theo thời gian kết thúc (Greedy)

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

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> movies(n);
    for (int i = 0; i < n; i++) {
        cin >> movies[i].first >> movies[i].second;
    }

    // Sắp xếp theo thời gian kết thúc
    sort(movies.begin(), movies.end(),
         [](pair<int,int> a, pair<int,int> b) {
             return a.second < b.second;
         });

    int cnt = 0;
    int lastEnd = -1e9;

    for (auto &m : movies) {
        // Chọn phim nếu nó bắt đầu sau khi phim trước kết thúc
        if (m.first >= lastEnd) {
            cnt++;
            lastEnd = m.second;
        }
    }

    cout << cnt;
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Đây là thuật toán Greedy tối ưu cho bài toán này. Ta sắp xếp tất cả các bộ phim theo thời gian kết thúc tăng dần. Giả sử ta đã chọn được một phim có thời gian kết thúc là t, để có thể xem được nhiều phim nhất, phim tiếp theo nên là phim có thời gian kết thúc sớm nhất trong số các phim còn lại mà bắt đầu sau thời điểm t. Việc chọn phim kết thúc sớm nhất để lại nhiều thời gian trống nhất cho các phim tiếp theo. Logic: Duyệt qua danh sách đã sắp xếp, nếu phim hiện tại bắt đầu >= thời gian kết thúc của phim đã chọn cuối cùng thì chọn phim đó.

Cách Sắp xếp theo thời gian kết thúc (Có xử lý重叠)

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

int main() {
    int n;
    cin >> n;

    vector<pair<int,int>> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i].first >> a[i].second;

    // Sắp xếp theo thời điểm kết thúc
    // Nếu cùng kết thúc thì ưu tiên bắt đầu sớm hơn (không bắt buộc nhưng tốt cho việc xử lý dữ liệu)
    sort(a.begin(), a.end(), [](auto &x, auto &y){
        if (x.second == y.second) return x.first < y.first;
        return x.second < y.second;
    });

    int cnt = 0;
    int last_end = -1;

    for (auto &p : a) {
        if (p.first >= last_end) {
            cnt++;
            last_end = p.second;
        }
    }

    cout << cnt;
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Phiên bản nâng cao của thuật toán Greedy. Sắp xếp theo thời gian kết thúc. Nếu hai phim có thời gian kết thúc bằng nhau, ta ưu tiên chọn phim có thời gian bắt đầu sớm hơn (dù logic chung là chọn phim nào cũng được nếu cùng kết thúc, trừ khi chúng giao nhau). Tuy nhiên, trong logic Greedy này, ta chỉ quan tâm đến việc phim tiếp theo phải bắt đầu sau thời điểm phim trước kết thúc. Việc xử lý equal trong sort giúp đảm bảo thứ tự duyệt ổn định.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này là bài toán kinh điển về 'Hoạt động không giao nhau' (Activity Selection Problem). Thuật toán Greedy bằng cách sắp xếp theo thời gian kết thúc là tối ưu.
• Tại sao phải sắp xếp theo thời gian kết thúc? Vì muốn để lại nhiều thời gian trống nhất cho các hoạt động tiếp theo, ta nên hoàn thành hoạt động hiện tại càng sớm càng tốt.
• Bài toán có thể được xem như tìm đường đi ngắn nhất trên đồ thị có hướng (nếu coi mỗi phim là một node và có đường nối từ phim A sang phim B nếu A kết thúc trước khi B bắt đầu). Thuật toán Greedy là cách hiệu quả nhất để giải quyết bài toán này với độ phức tạp O(n log n).

Lỗi thường gặp

• Sai lầm khi sắp xếp theo thời gian bắt đầu: Có thể chọn phải phim có thời gian dài (ví dụ 1->100) làm mất cơ hội xem các phim ngắn hơn (2->3, 3->4...).
• Quên xử lý dữ liệu đầu vào lớn: Với n ~ 10^6, cần sử dụng vector thay vì mảng tĩnh lớn, và tối ưu hóa việc nhập xuất (ví dụ dùng fast I/O trong C++).
• Lỗi logic khi xử lý thời điểm bắt đầu và kết thúc: Phải chắc chắn điều kiện là 'bắt đầu >= kết thúc trước đó' (nếu phim này bắt đầu chính xác lúc phim kia kết thúc thì có thể xem được).