Hướng giải của Lịch họp tối đa

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Đây là bài toán chọn khoảng không giao nhau cổ điển (Interval Scheduling). Thuật toán tham lam (Greedy) tối ưu như sau:

  1. Sắp xếp tất cả các cuộc họp theo thời gian kết thúc \(E_i\) tăng dần. Nếu thời gian kết thúc bằng nhau, sắp xếp theo thời gian bắt đầu tăng dần.
  2. Duyệt qua danh sách đã sắp xếp, chọn cuộc họp đầu tiên.
  3. Với mỗi cuộc họp tiếp theo, 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 cuộc họp chọn gần nhất, ta chọn cuộc họp này và cập nhật mốc kết thúc mới.

Độ phức tạp thời gian: \(O(N \log N)\).

Xem code mẫu C++ 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Meeting {
    long long start, end;
};

bool compare(const Meeting& x, const Meeting& y) {
    if (x.end != y.end) return x.end < y.end;
    return x.start < y.start;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    if (!(cin >> n)) return 0;
    vector<Meeting> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].start >> a[i].end;
    }
    sort(a.begin(), a.end(), compare);
    int ans = 0;
    long long last_end = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i].start >= last_end) {
            ans++;
            last_end = a[i].end;
        }
    }
    cout << ans << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.