Minimize Maximum Waiting Time for Students and Buses
Given N number of students and M number of buses with each of them having a capacity of C. The time of arrival of N students is given by an array arr[] where i’th index (1 ≤ i ≤ N) denotes the time of arrival of the ith student, the task is to find the smallest value of the maximum waiting time any student has to wait.
Note: Waiting time is the difference between his arrival and bus departure. It is always possible to accommodate all the students.
Examples:
Input: n = 4, m = 3, c = 3, arr[] = {5, 3, 7, 8}
Output: 1
Explanation:
- We can fill the first bus with 1 student arriving at time 3, so waiting time =0.
- We can fill the second bus with 1 student arriving at time 5, so waiting time =0.
- We can fill the third bus with 2 students arriving at time 7 and 8, so one student waits for 1 unit of time.
Input: n = 4, m = 2, c = 3, arr[] = {2, 3, 5, 10}
Output: 3
Explanation:
- We can fill the first bus with 3 students arriving at time 2, 3 and 5, so max waiting time = 3
- We can fill the second bus with 1 student arriving at time 10, so waiting time = 0
Approach: This can be solved with the following approach:
We can solve the problem by using Binary Search over the answer. Lets assume a function isPossible(X) that returns true if X can be the minimum of maximum waiting time. We can calculate the range in which the minimum of maximum waiting time can lie. Then, we will find the middle element of the range and check if it can a valid answer by calling isPossible() method. If it returns true, then our answer lies in the first half (including mid), else our answer lies in the second half (excluding mid).
Below are the steps involved:
- Sort the given array arr[].
- Initialize the low of the range in which the minimum of maximum waiting time can lie as 0.
- Initialize the high of the range in which the minimum of maximum waiting time can lie as arr[N-1] – arr[0], as this is the maximum waiting time possible.
- Using binary search, find mid of low and high as a minimum waiting time.
- For this waiting time, check whether if we can board all the students in M buses such that no student has to wait for time greater than mid.
- If mid waiting time is valid, update the answer and decrease the end to mid-1. Otherwise increase the start to mid+1.
Below is the implementation of the code:
C++
#include <bits/stdc++.h> using namespace std; // Function to check whether this waiting time // is right or not bool check( int mid, int m, int c, vector< int >& arr) { int count = 1, start = 0; for ( int i = 0; i < arr.size(); i++) { if (arr[i] - arr[start] > mid) { start = i; i--; count += 1; } } return count <= m; } // Function to find minimum wait time by // the student int minimumWaitTime( int N, int M, int C, vector< int >& arr) { // code here sort(arr.begin(), arr.end()); int low = 0, high = arr[N - 1] - arr[0]; int ans = 0; while (low <= high) { int mid = low + (high - low) / 2; // If mid is right, update the answer // and search in first half if (check(mid, M, C, arr)) { high = mid - 1; ans = mid; } // Search in second half else { low = mid + 1; } } return ans; } // Driver code int main() { // Inputs int n = 4; int m = 2; int c = 3; vector< int > arr = { 2, 3, 5, 10 }; // Function call cout << minimumWaitTime(n, m, c, arr); return 0; } |
Java
import java.util.Arrays; import java.util.List; public class Main { // Function to check whether this waiting time is right or not static boolean check( int mid, int m, int c, List<Integer> arr) { int count = 1 ; int start = 0 ; for ( int i = 0 ; i < arr.size(); i++) { if (arr.get(i) - arr.get(start) > mid) { start = i; i--; count++; } } return count <= m; } // Function to find minimum wait time by the student static int minimumWaitTime( int N, int M, int C, List<Integer> arr) { // Sorting the array arr.sort( null ); int low = 0 , high = arr.get(N - 1 ) - arr.get( 0 ); int ans = 0 ; while (low <= high) { int mid = low + (high - low) / 2 ; // If mid is right, update the answer and search in the first half if (check(mid, M, C, arr)) { high = mid - 1 ; ans = mid; } // Search in the second half else { low = mid + 1 ; } } return ans; } // Driver code public static void main(String[] args) { // Inputs int n = 4 ; int m = 2 ; int c = 3 ; List<Integer> arr = Arrays.asList( 2 , 3 , 5 , 10 ); // Function call System.out.println(minimumWaitTime(n, m, c, arr)); } } |
Python3
# Python Implementaiton: def check(mid, m, c, arr): count = 1 start = 0 for i in range ( len (arr)): if arr[i] - arr[start] > mid: start = i count + = 1 return count < = m def minimumWaitTime(N, M, C, arr): arr.sort() low = 0 high = arr[N - 1 ] - arr[ 0 ] ans = 0 while low < = high: mid = low + (high - low) / / 2 if check(mid, M, C, arr): high = mid - 1 ans = mid else : low = mid + 1 return ans n = 4 m = 2 c = 3 arr = [ 2 , 3 , 5 , 10 ] print (minimumWaitTime(n, m, c, arr)) # This code is contributed by Sakshi |
C#
using System; using System.Collections.Generic; class Program { // Function to check whether this waiting time // is right or not static bool Check( int mid, int m, int c, List< int > arr) { int count = 1, start = 0; for ( int i = 0; i < arr.Count; i++) { if (arr[i] - arr[start] > mid) { start = i; i--; count += 1; } } return count <= m; } // Function to find minimum wait time by // the student static int MinimumWaitTime( int N, int M, int C, List< int > arr) { arr.Sort(); int low = 0, high = arr[N - 1] - arr[0]; int ans = 0; while (low <= high) { int mid = low + (high - low) / 2; // If mid is right, update the answer // and search in first half if (Check(mid, M, C, arr)) { high = mid - 1; ans = mid; } // Search in second half else { low = mid + 1; } } return ans; } // Driver code static void Main( string [] args) { // Inputs int n = 4; int m = 2; int c = 3; List< int > arr = new List< int > { 2, 3, 5, 10 }; // Function call Console.WriteLine(MinimumWaitTime(n, m, c, arr)); } } |
Javascript
// Function to check whether this waiting time // is right or not function check(mid, m, c, arr) { let count = 1, start = 0; for (let i = 0; i < arr.length; i++) { if (arr[i] - arr[start] > mid) { start = i; i--; count += 1; } } return count <= m; } // Function to find minimum wait time by the student function minimumWaitTime(N, M, C, arr) { arr.sort((a, b) => a - b); let low = 0, high = arr[N - 1] - arr[0]; let ans = 0; while (low <= high) { let mid = low + Math.floor((high - low) / 2); // If mid is right, update the answer // and search in first half if (check(mid, M, C, arr)) { high = mid - 1; ans = mid; } // Search in second half else { low = mid + 1; } } return ans; } // Driver code // Inputs let n = 4; let m = 2; let c = 3; let arr = [2, 3, 5, 10]; // Function call console.log(minimumWaitTime(n, m, c, arr)); |
3
Time Complexity: O(N*log (max(arr[i]))), where N is the length of input array
Auxiliary Space: O(N)