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

แนวคิด

ในส่วนที่เกี่ยวกับอาร์เรย์ของงานที่กำหนดซึ่งมีข้อกำหนดด้านเวลาต่างกัน มีผู้รับมอบหมายที่เหมือนกันจำนวน k ราย และเรายังได้รับแจ้งด้วยว่าผู้รับมอบหมายใช้เวลาเท่าใดในการทำงานหนึ่งหน่วยของงาน งานของเราคือกำหนดเวลาขั้นต่ำในการทำงานทั้งหมดให้เสร็จสิ้นโดยมีข้อจำกัดดังต่อไปนี้

ข้อจำกัดแรกคือสามารถกำหนดผู้รับโอนได้เฉพาะงานที่ต่อเนื่องกัน

ตัวอย่างเช่น ในที่นี้ ผู้รับมอบหมายสามารถมอบหมายงานที่ตำแหน่ง 1 และ 2 ได้ แต่ไม่ใช่ที่ตำแหน่ง 3 ในอาร์เรย์
ข้อจำกัดที่สองคือผู้รับมอบหมายสองคนไม่สามารถแบ่งปัน (หรือมอบหมายร่วมกัน) งานได้ ซึ่งหมายความว่างานไม่สามารถมอบหมายบางส่วนให้กับผู้รับมอบหมายรายหนึ่งและบางส่วนให้กับผู้อื่นได้บางส่วน

อินพุต

k - ระบุจำนวนผู้รับมอบหมายที่พร้อมใช้งาน

t − ระบุเวลาที่ผู้ได้รับมอบหมายทำงานให้เสร็จหนึ่งหน่วย

JOB[] - ระบุอาร์เรย์ที่แสดงถึงข้อกำหนดด้านเวลาของงานที่แตกต่างกัน

อินพุต

k = 2, t = 4, JOB[] = {5, 6, 12}

ผลลัพธ์

เวลาขั้นต่ำที่จำเป็นในการทำงานทั้งหมดให้เสร็จสิ้นคือ 48

มีผู้รับมอบอำนาจ 2 คน เราได้รับเวลานี้โดยมอบหมาย {5, 6} ให้กับผู้รับมอบหมายคนแรกและ {12} ให้กับผู้รับมอบหมายที่สอง

อินพุต

k = 4, t = 5, JOB[] = {12, 6, 9, 15, 5, 9}

ผลลัพธ์

เราได้เวลานี้โดยมอบหมาย {12} {6, 9} {15} และ {5, 9}

วิธีการ

ตอนนี้แนวคิดคือการนำ Binary Search ไปใช้ สมมติว่าเรามีฟังก์ชัน (เช่น isPossible()) ที่ระบุว่าเป็นไปได้หรือไม่ที่จะทำงานทั้งหมดให้เสร็จสิ้นภายในเวลาที่กำหนดและจำนวนผู้ได้รับมอบหมาย ที่นี่ เราสามารถแก้ปัญหานี้ได้โดยทำการค้นหาแบบไบนารีเพื่อหาคำตอบ จะเห็นได้ว่าถ้าจุดกึ่งกลางของการค้นหาแบบไบนารีเป็นไปไม่ได้ ให้ค้นหาในครึ่งหลัง มิฉะนั้นจะค้นหาในครึ่งแรก ขอบเขตล่างสำหรับการค้นหาไบนารีสำหรับเวลาที่เล็กที่สุดสามารถตั้งค่าเป็น 0 ที่นี่ ขอบเขตบนสามารถรับได้โดยเพิ่มเวลางานที่ให้มาทั้งหมด

ปัจจุบันมีคำถามเกิดขึ้นว่าจะใช้ isPossible() อย่างไร เราสามารถใช้ฟังก์ชันนี้ได้โดยใช้ Greedy Approach เนื่องจากเราต้องการทราบว่าสามารถทำงานทั้งหมดให้เสร็จภายในเวลาที่กำหนดได้หรือไม่ เราจึงตรวจสอบงานทั้งหมดและดูแลการมอบหมายงานให้กับผู้รับมอบหมายปัจจุบันทีละงาน ในขณะเดียวกัน เราควรจำไว้ว่าสามารถมอบหมายงานได้ภายในระยะเวลาที่กำหนด ในขณะนั้น เมื่อเวลาที่ใช้โดยผู้รับมอบหมายปัจจุบันข้ามเวลาที่กำหนด ให้สร้างผู้รับมอบหมายใหม่และเริ่มมอบหมายงานให้กับผู้รับมอบหมายนั้น จะเห็นได้ว่าหากจำนวนผู้ได้รับมอบหมายเพิ่มขึ้น ขอบคุณ ให้คืนค่าเท็จ ไม่เช่นนั้นให้คืนค่าเป็น จริง

ตัวอย่าง

// C++ program to find minimum time to finish all jobs with
// given number of assignees
#include<bits/stdc++.h>
using namespace std;
// Shows utility function to get maximum element in job1[0..n1-1]
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;
}
// Now returns true if it is possible to finish jobs1[] within
// given time 'time1'
bool isPossible(int time1, int K1, int job1[], int n1){
   // Here, cnt1 is count of current assignees required for jobs
   int cnt1 = 1;
   int curr_time1 = 0; // Indicates time assigned to current
   //assignee
   for (int i = 0; i < n1;){
      // Now if time assigned to current assignee exceeds max1,
      // increment count1 of assignees.
      if (curr_time1 + job1[i] > time1) {
         curr_time1 = 0;
         cnt1++;
      }
      else { // Else add time of job to current time and move
         // to next job.
         curr_time1 += job1[i];
         i++;
      }
   }
   //Now returns true if count is smaller than k
   return (cnt1 <= K1);
}
// Here, returns minimum time required to finish given array of
//jobs
// K1 --> number of assignees
// T1 --> Time required by every assignee to finish 1 unit
// n1 --> Number of jobs
int findMinTime(int K1, int T1, int job1[], int n1){
   // Used to set start and end for binary search
   // end provides an upper limit on time1
   int end1 = 0, start1 = 0;
   for (int i = 0; i < n1; ++i)
      end1 += job1[i];
   int ans1 = end1; // Used to initialize answer
   // Determine the job that takes maximum time
   int job_max1 = getMax(job1, n1);
   // Perform binary search for minimum feasible time
   while (start1 <= end1){
      int mid1 = (start1 + end1) / 2;
      // Now if it is possible to complete jobs in mid time
      if (mid1 >= job_max1 && isPossible(mid1, K1, job1, n1)){
         ans1 = min(ans1, mid1); // Used to update answer
         end1 = mid1 - 1;
      }
      else
         start1 = mid1 + 1;
   }
   return (ans1 * T1);
}
// Driver program
int main(){
   int job1[] = {12, 6, 9, 15, 5, 9};
   // int job1[] = {5, 6, 12};
   int n1 = sizeof(job1)/sizeof(job1[0]);
   int k1=4, T1=5;
   // int k1=2, T1=4;
   cout << findMinTime(k1, T1, job1, n1) << endl;
   return 0;
}