C++-এ দেয়া কনস্ট্রেইন্টসহ সব জব ফিনিশ করার ন্যূনতম সময়

জবের একটি অ্যারে (প্রতিটির টাইম রিকোয়ারমেন্ট), k সংখ্যক একই অ্যাসাইনি, এবং একটি অ্যাসাইনির প্রতি ইউনিট জবের টাইম t দেওয়া আছে। কনস্ট্রেইন্ট: (১) অ্যাসাইনি শুধু কন্টিগুয়াস জব নিতে পারে, (২) এক জব একাধিক অ্যাসাইনির মধ্যে শেয়ার করা যাবে না। সব জব ফিনিশ করার ন্যূনতম সময় বের করতে হবে।

উদাহরণ

k=2, t=4, JOB[]={5,6,12}  →  48
(অ্যাসাইনি ১: {5,6}, অ্যাসাইনি ২: {12})

অ্যালগরিদম (বাইনারি সার্চ + গ্রিডি)

• বাইনারি সার্চ সময় T এর ওপর: লো=০, হাই=সব জবের যোগফল।
• isPossible(time): গ্রিডি করে বর্তমান অ্যাসাইনির কাছে যতক্ষণ সম্ভব জব দিন, টাইম লিমিট পার করলে নতুন অ্যাসাইনি।
• যদি অ্যাসাইনির সংখ্যা ≤ k হয়, তবে সম্ভব।
• ফাইনাল আন্সওয়ার = min_time * t।

C++ প্রোগ্রাম

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

int getMax(int arr[], int n) {
    int mx = arr[0];
    for (int i=1;imx) mx=arr[i];
    return mx;
}

bool isPossible(int time, int K, int job[], int n) {
    int cnt = 1, curr = 0;
    for (int i=0;i time) { curr=0; cnt++; }
        else { curr += job[i]; i++; }
    }
    return cnt <= K;
}

int findMinTime(int K, int T, int job[], int n) {
    int start=0, end=0;
    for (int i=0;i= jobMax && isPossible(mid, K, job, n)) {
            ans = min(ans, mid);
            end = mid - 1;
        } else start = mid + 1;
    }
    return ans * T;
}

int main() {
    int job[] = {12,6,9,15,5,9};
    int n = sizeof(job)/sizeof(job[0]);
    int k=4, T=5;
    cout << findMinTime(k, T, job, n) << endl;
    return 0;
}

আউটপুট: 75