Tìm thời gian tối thiểu hoàn thành tất cả công việc với ràng buộc trong C++

Khái niệm

Cho mảng công việc với thời gian yêu cầu khác nhau, k người gán việc giống nhau, và thời gian t để một người làm một đơn vị công việc. Tìm thời gian tối thiểu hoàn thành tất cả công việc với ràng buộc:

Người làm chỉ được gán các công việc liền kề (contiguous).
Một công việc không thể chia cho nhiều người.

Ví dụ 1

Đầu vào: k = 2, t = 4, JOB[] = {5, 6, 12}

Đầu ra: 48

Gán {5,6} cho người 1, {12} cho người 2. Thời gian = max(11,12)*4 = 48.

Ví dụ 2

Đầu vào: k = 4, t = 5, JOB[] = {12, 6, 9, 15, 5, 9}

Đầu ra: 75

Gán {12}, {6,9}, {15}, {5,9}.

Phương pháp

Dùng Tìm kiếm nhị phân (Binary Search). Hàm isPossible(time) kiểm tra có thể hoàn thành trong 'time' không. Duyệt công việc, gán cho người hiện tại cho đến khi vượt quá time, thì sang người mới. Nếu số người > k → false.

Binary search trên khoảng [0, tổng thời gian tất cả công việc]. Lower bound = max thời gian một công việc.

Ví dụ

#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, 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;
}