หาเวลาน้อยที่สุดเพื่อทำงานทั้งหมดภายใต้เงื่อนไขที่กำหนดใน C++

แนวคิด

กำหนดอาร์เรืองานที่แต่ละงานใช้เวลาต่างกัน มี k คนรับมอบหมาย (identical assignees) และทราบว่า 1 คนใช้เวลา t ต่อ 1 หน่วยงาน หาเวลาน้อยที่สุดเพื่อทำงานทั้งหมดภายใต้เงื่อนไข:

1. คนรับมอบหมายได้รับเฉพาะงานที่ติดกัน (contiguous jobs)
2. ไม่มี 2 คนแบ่งปันงานเดียวกัน (งานไม่สามารถแบ่งให้หลายคนได้)

ตัวอย่างที่ 1

Input: k = 2, t = 4, JOB[] = {5, 6, 12}
Output: 48
มอบ {5,6} ให้คนแรก (11 หน่วย × 4 = 44) และ {12} ให้คนที่สอง (12 × 4 = 48) → max = 48

ตัวอย่างที่ 2

Input: k = 4, t = 5, JOB[] = {12, 6, 9, 15, 5, 9}
Output: 75
มอบ {12}, {6,9}, {15}, {5,9} → max sum = 15 → 15 × 5 = 75

แนวทางแก้ปัญหา: Binary Search + Greedy

1. ฟังก์ชัน isPossible(time): ตรวจสอบว่าเสร็จภายในเวลา time ได้ไหม โดยมอบงานติดกันให้คนปัจจุบันจนเกินเวลา → สร้างคนใหม่
2. Binary Search ช่วง [0, sum(jobs)] หาเวลาต่ำสุดที่ isPossible = true
3. คูณด้วย t ได้คำตอบสุดท้าย

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

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

int getMax(int arr1[], int n1) {
    int result1 = arr1[0];
    for (int i = 1; i < n1; i++)
        if (arr1[i] > result1) result1 = arr1[i];
    return result1;
}

bool isPossible(int time1, int K1, int job1[], int n1) {
    int cnt1 = 1;
    int curr_time1 = 0;
    for (int i = 0; i < n1; ) {
        if (curr_time1 + job1[i] > time1) {
            curr_time1 = 0;
            cnt1++;
        } else {
            curr_time1 += job1[i];
            i++;
        }
    }
    return (cnt1 <= K1);
}

int findMinTime(int K1, int T1, int job1[], int n1) {
    int end1 = 0, start1 = 0;
    for (int i = 0; i < n1; ++i) end1 += job1[i];
    int ans1 = end1;
    int job_max1 = getMax(job1, n1);
    
    while (start1 <= end1) {
        int mid1 = (start1 + end1) / 2;
        if (mid1 >= job_max1 && isPossible(mid1, K1, job1, n1)) {
            ans1 = min(ans1, mid1);
            end1 = mid1 - 1;
        } else
            start1 = mid1 + 1;
    }
    return (ans1 * T1);
}

int main() {
    int job1[] = {12, 6, 9, 15, 5, 9};
    int n1 = sizeof(job1) / sizeof(job1[0]);
    int k1 = 4, T1 = 5;
    cout << findMinTime(k1, T1, job1, n1) << endl;
    return 0;
}

ผลลัพธ์

75