หาความเร็วขั้นต่ำเพื่อทำงานให้เสร็จทันเวลาด้วย C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ arr[] (งานแต่ละชุด) และ H ชั่วโมง หาความเร็วขั้นต่ำ (งาน/ชั่วโมง) เพื่อทำให้เสร็จภายใน H ชั่วโมง

เงื่อนไข: ถ้าทำชุดไหนเสร็จก่อน 1 ชั่วโมง ต้องรอจนครบชั่วโมง

ตัวอย่าง

อินพุต

arr[] = {4, 5, 1, 7, 8}, H = 5

เอาต์พุต

8

คำอธิบาย

ต้องทำชุดที่มากที่สุด (8) ให้เสร็จใน 1 ชั่วโมง → speed = 8

วิธีแก้ปัญหา

Binary Search บนความเร็ว 1 ถึง max(arr)

เช็คว่า speed ใดทำให้เสร็จทัน: time = Σ ceil(arr[i] / speed) ≤ H

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

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

bool canDoJobInTime(int A[], int n, int H, int speed) {
    int timeTaken = 0;
    for (int i = 0; i < n; ++i)
        timeTaken += (A[i] - 1) / speed + 1;  // ceil division
    return timeTaken <= H;
}

int calcJobMinSpeed(int A[], int n, int H) {
    if (H < n) return -1;  // ไม่พอเวลาอย่างน้อย 1 ชม./ชุด
    
    int maxJob = *max_element(A, A + n);
    int lo = 1, hi = maxJob;
    
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (!canDoJobInTime(A, n, H, mid))
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

int main() {
    int A[] = {3, 6, 7, 11}, H = 8;
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Minimum speed to finish all jobs in time is " << calcJobMinSpeed(A, n, H);
    return 0;
}

เอาต์พุต

Minimum speed to finish all jobs in time is 4

สรุป

Binary Search บนคำตอบ (Monotonic Property) Complexity O(N log MaxVal)