โปรแกรม C++ หาจำนวนหนังที่ผู้เข้าร่วมดูได้เต็มที่ในงานเทศกาลภาพยนตร์

มีเทศกาลภาพยนตร์ หลายเรื่อง ผู้เข้าร่วมอยากดูหนังมากที่สุดโดยไม่ทับซ้อนเวลา หาจำนวนหนังสูงสุดที่ดูจบได้

โครงสร้างข้อมูล

• struct Movie: timeBegin (เริ่ม), duration (ระยะเวลา), timeEnd (จบ = เริ่ม + ระยะเวลา)
• struct Festival: count (จำนวนหนัง), vector movies

ตัวอย่าง

Input: timeBegin = {1,3,0,5,5,8,8}, duration = {3,2,2,4,3,2,3}, n = 7

Output: 4

คำอธิบาย: ดูได้ 4 เรื่องเต็มที่ (Activity Selection / Greedy by end time)

อัลกอริทึม: Greedy (Activity Selection)

• initialize(timeBegin, duration, count): สร้าง Festival, คำนวณ timeEnd, เก็บใน movies
• solve(fest):
  • เรียง movies ตาม timeEnd (operator<)
  • timeEnd = -1, res = 0
  • วนหนังทุกเรื่อง: ถ้า movie.timeBegin >= timeEnd → เลือกดู (res++, timeEnd = movie.timeEnd)

ตัวอย่างโค้ด C++

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

struct Movie {
    int timeBegin, duration, timeEnd;
    bool operator<(const Movie& another) const {
        return timeEnd < another.timeEnd;
    }
};

struct Festival {
    int count;
    vector<Movie> movies;
};

Festival* initialize(int timeBegin[], int duration[], int count) {
    Festival* filmFestival = new Festival;
    filmFestival->count = count;
    for (int i = 0; i < count; i++) {
        Movie temp;
        temp.timeBegin = timeBegin[i];
        temp.duration = duration[i];
        temp.timeEnd = timeBegin[i] + duration[i];
        filmFestival->movies.push_back(temp);
    }
    return filmFestival;
}

int solve(Festival* fest) {
    int res = 0;
    sort(fest->movies.begin(), fest->movies.end());
    int timeEnd = -1;
    for (int i = 0; i < fest->count; i++) {
        if (fest->movies[i].timeBegin >= timeEnd) {
            res++;
            timeEnd = fest->movies[i].timeEnd;
        }
    }
    return res;
}

int main() {
    int timeBegin[] = {1, 3, 0, 5, 5, 8, 8};
    int duration[] = {3, 2, 2, 4, 3, 2, 3};
    Festival* fest = initialize(timeBegin, duration, 7);
    cout << solve(fest) << endl;
    return 0;
}

Input

timeBegin[] = {1,3,0,5,5,8,8}; duration[] = {3,2,2,4,3,2,3}; n=7

Output

4