Tối đa số phim xem được tại Liên hoan phim (Film Festival) trong C++

Cho danh sách phim: thời gian bắt đầu, độ dài. Tìm số phim tối đa xem được không chồng chéo (greedy theo thời gian kết thúc sớm nhất).

Ví dụ

Đầu vào: timeBegin[] = {1,3,0,5,5,8,8}, duration[] = {3,2,2,4,3,2,3}, n=7

Đầu ra: 4

Giải thích: Phim kết thúc sớm: (0,2), (3,5), (5,9), (8,11) → 4 phim.

Phương pháp: Greedy + Sort theo thời gian kết thúc

• Tính end = begin + duration cho mỗi phim.
• Sort mảng phim theo end tăng dần.
• Duyệt: nếu begin >= lastEnd → chọn phim, cập nhật lastEnd = end.

Ví dụ mã C++

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

struct Movie {
    int begin, duration, end;
    bool operator<(const Movie& other) const { return end < other.end; }
};

struct Festival {
    int count;
    vector movies;
};

Festival* initialize(int begin[], int dur[], int n) {
    Festival* f = new Festival();
    f->count = n;
    for (int i=0; imovies.push_back(m);
    }
    return f;
}

int solve(Festival* f) {
    sort(f->movies.begin(), f->movies.end());
    int lastEnd = -1, res = 0;
    for (auto &m: f->movies) {
        if (m.begin >= lastEnd) {
            res++;
            lastEnd = m.end;
        }
    }
    return res;
}

int main() {
    int begin[] = {1,3,0,5,5,8,8};
    int dur[] = {3,2,2,4,3,2,3};
    Festival* fest = initialize(begin, dur, 7);
    cout << "Max movies: " << solve(fest) << endl;
    return 0;
}

Đầu ra chương trình

4