C++ প্রোগ্রাম: ফিল্ম ফেস্টিভ্যালে একজন অংশগ্রহী সম্পূর্ণ কতগুলো সিনেমা দেখতে পারে

মান ليजिए একটি ফিল্ম ফেস্টিভ্যাল চলছে যেতে వివिध দেশের বিভিন্ন সিনেমা প্রদর্শন করা হচ্ছে। এখন, একজন অংশগ্রহী ওভারল্যাপ না করে সর্বোচ্চ সংখ্যক সিনেমা দেখতে চান এবং আমাদের তাঁকে সাহায্য করতে হবে কতগুলো সিনেমা তারা সম্পূর্ণ দেখতে পারেন তা বের করতে।

Movie নামে একটি স্ট্রাকচার আছে যাতে নিচের মেম্বারগুলো রয়েছে:-

সিনেমার শুরু করার সময়।
সিনেমার সময়কাল।
সিনেমার শেষ করার সময়।

Festival নামে আরেকটি স্ট্রাকচার আছে যাতে নিচের মেম্বারগুলো রয়েছে:-

ফেস্টিভ্যালে সিনেমার সংখ্যা।
Movie টাইপের একটি অ্যারে যেনার আকার ফেস্টিভ্যালে সিনেমার সংখ্যার সমান।

আমাদের একটি Festival অবজেক্ট তৈরি এবং ইনিশিয়ালাইজ করতে হবে 'timeBegin' এবং 'duration' নামের দুটি অ্যারে দিয়ে যাতে যথাক্রমে সিনেমার শুরু করার সময় এবং সময়কাল রয়েছে। একটি পূর্ণসংখ্যা n মোট সিনেমার সংখ্যা বোঝায় এবং এটিও অবজেক্ট ইনিশিয়ালাইজ করতে ব্যবহৃত হয়। আমরা আরও সেই অবজেক্টটি ব্যবহার করব একটি অংশগ্রহী সম্পূর্ণ কতগুলো সিনেমা দেখতে পারে তা গণনা করতে।

তাই, যদি ইনপুট হয় timeBegin = {1, 3, 0, 5, 5, 8, 8}, duration = {3, 2, 2, 4, 3, 2, 3}, n = 7, তবে আউটপুট হবে 4।

অংশগ্রহী সেই ফেস্টিভ্যালে মোট ৪টি সিনেমা সম্পূর্ণ দেখতে পারেন।

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:-

struct Movie {-
- তিনটি মেম্বার ভেরিয়েবল ডিফাইন করুন timeBegin, duration, timeEnd
- একটি অপারেটর '<' ওভারলোড করুন, এটি another নামে একটি Movie টাইপের ভেরিয়েবল নেবে।
  - return timeEnd < another.timeEnd
struct Festival {-
- একটি মেম্বার count ডিফাইন করুন
- movies নামে একটি অ্যারে ডিফাইন করুন যেটি Movie টাইপের আইটেম ধারণ করে
initialize() নামে একটি ফাংশন ডিফাইন করুন। এটি timeBegin এবং timeEnd অ্যারে এবং একটি ইন্টিজার n নেবে।
- filmFestival := একটি নতুন Festival অবজেক্ট
- filmFestival-এর count := count
- i := 0 দিয়ে ইনিশিয়ালাইজ করুন, যখন i < count, আপডেট করুন (i ১ বাড়িয়ে), করুন:-
  - temp := Movie টাইপের একটি নতুন অবজেক্ট
  - temp-এর timeBegin := timeBegin[i]
  - temp-এর duration := duration[i]
  - temp-এর timeEnd := timeBegin[i] + duration[i]
  - temp কে filmFestival-এর movies অ্যারেতে ইনসার্ট করুন
- filmFestival রিটার্ন করুন
solve() নামে একটি ফাংশন ডিফাইন করুন, এটি fest নামে একটি Festival টাইপের ভেরিয়েবল নেবে।
- res := 0
- fest-এর movies অ্যারে সর্ট করুন
- timeEnd := -1
- i := 0 দিয়ে ইনিশিয়ালাইজ করুন, যখন i < fest->count, আপডেট করুন (i ১ বাড়িয়ে), করুন:-
  - যদি fest-এর movies[i]-এর timeBegin >= timeEnd, তবে -
    - (res কে ১ বাড়ান)
    - timeEnd := fest-এর movies[i]-এর timeEnd
- res রিটার্ন করুন

উদাহরণ

বेहतर বুঝতে নিচের ইমপ্লিমেন্টেশনটি দেখুন:-

#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 argc, char *argv[]) { 
    int timeBegin[] = {1, 3, 0, 5, 5, 8, 8}; 
    int duration[] = {3, 2, 2, 4, 3, 2, 3}; 
    Festival * fest; 
    fest = initialize(timeBegin,duration, 7); 
    cout << solve(fest) << endl; 
    return 0; 
}

ইনপুট

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