fork download
copy 
  1. // C++ program to find minimum time to finish all jobs with 
  2. // given number of assignees 
  3. #include<bits/stdc++.h> 
  4. using namespace std; 
  5.  
  6. // Utility function to get maximum element in job[0..n-1] 
  7. int getMax(int arr[], int n) 
  8. { 
  9. int result = arr[0]; 
  10. for (int i=1; i<n; i++) 
  11. 	if (arr[i] > result) 
  12. 		result = arr[i]; 
  13. 	return result; 
  14. } 
  15.  
  16. // Returns true if it is possible to finish jobs[] within 
  17. // given time 'time' 
  18. bool isPossible(int time, int K, int job[], int n) 
  19. { 
  20. 	// cnt is count of current assignees required for jobs 
  21. 	int cnt = 1; 
  22.  
  23. 	int curr_time = 0; // time assigned to current assignee 
  24.  
  25. 	for (int i = 0; i < n;) 
  26. 	{ 
  27. 		// If time assigned to current assignee exceeds max, 
  28. 		// increment count of assignees. 
  29. 		if (curr_time + job[i] > time) { 
  30. 			curr_time = 0; 
  31. 			cnt++; 
  32. 		} 
  33. 		else { // Else add time of job to current time and move 
  34. 			// to next job. 
  35. 			curr_time += job[i]; 
  36. 			i++; 
  37. 		} 
  38. 	} 
  39.  
  40. 	// Returns true if count is smaller than k 
  41. 	return (cnt <= K); 
  42. } 
  43.  
  44. // Returns minimum time required to finish given array of jobs 
  45. // k --> number of assignees 
  46. // T --> Time required by every assignee to finish 1 unit 
  47. // m --> Number of jobs 
  48. int findMinTime(int K, int T, int job[], int n) 
  49. { 
  50. 	// Set start and end for binary search 
  51. 	// end provides an upper limit on time 
  52. 	int end = 0, start = 0; 
  53. 	for (int i = 0; i < n; ++i) 
  54. 		end += job[i]; 
  55.  
  56. 	int ans = end; // Initialize answer 
  57.  
  58. 	// Find the job that takes maximum time 
  59. 	int job_max = getMax(job, n); 
  60.  
  61. 	// Do binary search for minimum feasible time 
  62. 	while (start <= end) 
  63. 	{ 
  64. 		int mid = (start + end) / 2; 
  65.  
  66. 		// If it is possible to finish jobs in mid time 
  67. 		if (mid >= job_max && isPossible(mid, K, job, n)) 
  68. 		{ 
  69. 			ans = min(ans, mid); // Update answer 
  70. 			end = mid - 1; 
  71. 		} 
  72. 		else
  73. 			start = mid + 1; 
  74. 	} 
  75.  
  76. 	return (ans * T); 
  77. } 
  78.  
  79. // Driver program 
  80. int main() 
  81. { 
  82. 	int job[] = {10, 15,4}; 
  83. 	int n = sizeof(job)/sizeof(job[0]); 
  84. 	int k = 2, T = 5; 
  85. 	cout << findMinTime(k, T, job, n) << endl; 
  86. 	return 0; 
  87. } 
  88.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
95
https://ideone.com/QovK7r
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!