Time Crunch Challenge
Beginner for Beginner is organizing a hackathon consisting of N sections, each containing K questions. The duration of the hackathon is H hours.
Each participant can determine their speed of solving questions, denoted as S (S = questions-per-hour). During each hour, a participant can choose a section and solve S problems. If a section has fewer than S questions, the participant will not solve any additional questions from that section during that hour.
The goal is for the participant to solve the questions at a slower pace while still completing all the questions before the hackathon ends, the task is to find the S such that ensures the participant will solve all the questions within H hours.
Examples:
Input: section = [ 2, 4, 2, 4, 5], H = 8
Output: 3
Explanation: Participate will solve 3 questions per hour to solve all the questions within 8 hours.Input: section = [ 8, 11, 18, 20], H = 10
Output: 7
Explanation: Participate will solve 7 questions per hour to solve all the questions within 10 hours.
Naïve Approach: The basic way to solve the problem is as follows:
- Check if
H
is equal to the number of sections. - If true, return the maximum time needed for any section.
- Calculate the minimum possible solving speed (k_min) by dividing the total time required to solve all sections by
H
. - Calculate the maximum possible solving speed (k_max) by finding the maximum time needed for any section using
max_element
. - Iterate through possible solving speeds from
k_min
tok_max
. - Calculate the total hours required to solve all sections at each speed.
- If total hours are equal
H
, return the current speedk
. - If no valid solution is found, return -1.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; class Solution { public : int minSolvingSpeed(vector< int >& sections, int h) { if (h == sections.size()) { return *max_element(sections.begin(), sections.end()); } int k_min = ceil ( static_cast < double >(accumulate( sections.begin(), sections.end(), 0)) / h); int k_max = *max_element(sections.begin(), sections.end()); for ( int k = k_min; k <= k_max; k++) { int hours_to_solve = 0; for ( int section : sections) { hours_to_solve += ceil ( static_cast < double >(section) / k); } if (hours_to_solve == h) { return k; } } return -1; } }; // Drivers code int main() { Solution solution; vector< int > sections = { 8, 11, 18, 20 }; int h = 10; // Function Call int result = solution.minSolvingSpeed(sections, h); cout << "Minimum eating speed required: " << result << endl; return 0; } |
Java
//Java Code Implementation of the above approach. import java.util.*; class Solution { public int minSolvingSpeed(List<Integer> sections, int h) { // If the required hours are the same as the number of sections, // we can just return the maximum time section since each section takes 1 hour. if (h == sections.size()) { return Collections.max(sections); } // Calculate the minimum and maximum possible eating speeds (k) based on total time int k_min = ( int ) Math.ceil(sections.stream().mapToDouble(Integer::doubleValue).sum() / h); int k_max = Collections.max(sections); // Iterate through possible eating speeds within the calculated range for ( int k = k_min; k <= k_max; k++) { int hours_to_solve = 0 ; // Calculate the total time required to solve all sections at the current speed (k) for ( int section : sections) { hours_to_solve += Math.ceil(( double ) section / k); } // If the calculated total time matches the target hours, return the current speed (k) if (hours_to_solve == h) { return k; } } // If no suitable speed is found, return -1 return - 1 ; } } public class Main { public static void main(String[] args) { Solution solution = new Solution(); List<Integer> sections = Arrays.asList( 8 , 11 , 18 , 20 ); int h = 10 ; // Call the minSolvingSpeed function to get the minimum eating speed required int result = solution.minSolvingSpeed(sections, h); // Print the result System.out.println( "Minimum eating speed required: " + result); } } // This code is contributed by chinmaya121221 |
Python3
# Python Code Implementation of the above approach. class Solution: def min_solving_speed( self , sections, h): if h = = len (sections): return max (sections) # Equivalent to ceil(sum(sections) / h) in C++ k_min = - ( - sum (sections) / / h) k_max = max (sections) for k in range (k_min, k_max + 1 ): hours_to_solve = 0 for section in sections: # Equivalent to ceil(section / k) in C++ hours_to_solve + = - ( - section / / k) if hours_to_solve = = h: return k return - 1 # Driver code if __name__ = = "__main__" : solution = Solution() sections = [ 8 , 11 , 18 , 20 ] h = 10 # Function Call result = solution.min_solving_speed(sections, h) print ( "Minimum eating speed required:" , result) # This code is contributed by prasad264 |
C#
using System; using System.Collections.Generic; using System.Linq; public class Solution { public int MinSolvingSpeed(List< int > sections, int h) { // If h is equal to the number of sections, // return the maximum section time if (h == sections.Count) { return sections.Max(); } // Calculate the minimum possible speed (k_min) // using ceil of average time taken to solve all sections int k_min = ( int )Math.Ceiling(( double )sections.Sum() / h); // Find the maximum section time (k_max) int k_max = sections.Max(); // Iterate through possible speeds from k_min to k_max for ( int k = k_min; k <= k_max; k++) { int hoursToSolve = 0; // Calculate total hours required to solve all sections foreach ( int section in sections) { hoursToSolve += ( int )Math.Ceiling(( double )section / k); } // If total hours match the given hours (h), // return the current speed (k) if (hoursToSolve == h) { return k; } } // If no matching speed is found, return -1 return -1; } } class Program { static void Main() { Solution solution = new Solution(); List< int > sections = new List< int > { 8, 11, 18, 20 }; int h = 10; // Function Call int result = solution.MinSolvingSpeed(sections, h); Console.WriteLine( "Minimum eating speed required: " + result); } } |
Javascript
class Solution { minSolvingSpeed(sections, h) { // If the required hours are the same as the number of sections, // we can just return the maximum time section since each section takes 1 hour. if (h === sections.length) { return Math.max(...sections); } // Calculate the minimum and maximum possible eating speeds (k) based on total time const k_min = Math.ceil(sections.reduce((acc, section) => acc + section, 0) / h); const k_max = Math.max(...sections); // Iterate through possible eating speeds within the calculated range for (let k = k_min; k <= k_max; k++) { let hours_to_solve = 0; // Calculate the total time required to solve all sections at the current speed (k) for (let i = 0; i < sections.length; i++) { hours_to_solve += Math.ceil(sections[i] / k); } // If the calculated total time matches the target hours, return the current speed (k) if (hours_to_solve === h) { return k; } } // If no suitable speed is found, return -1 return -1; } } const solution = new Solution(); const sections = [8, 11, 18, 20]; const h = 10; // Call the minSolvingSpeed function to get the minimum eating speed required const result = solution.minSolvingSpeed(sections, h); // Print the result console.log( "Minimum eating speed required: " + result); |
Minimum eating speed required: 7
Time Complexity: O(n (max K −min K))
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
We can solve this problem using Binary Search
Follow the below steps to solve the problem:
- Initialize the left pointer to 1 and the right pointer to the maximum value in the section vector.
- While the left pointer is less than the right pointer, repeat steps 3-5.
- Calculate the midpoint as the average of the left and right pointers.
- Check if the participant can solve all the questions within h hours at the current midpoint speed using the canSolveAll function. If true, update the right pointer to the midpoint. Otherwise, update the left pointer to midpoint + 1.
- Repeat steps 3-4 until the left pointer becomes equal to the right pointer.
- Return the left pointer as the minimum solving speed required to solve all the questions within H hours.
- we get then our final result.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <algorithm> #include <iostream> #include <vector> using namespace std; bool canSolveAll(vector< int >& sections, int speed, int h) { int time = 0; for ( int section : sections) { time += (section - 1) / speed + 1; if ( time > h) { return false ; } } return true ; } int minSolvingSpeed(vector< int >& sections, int h) { int left = 1; int right = *max_element(sections.begin(), sections.end()); while (left < right) { int mid = (left + right) / 2; if (canSolveAll(sections, mid, h)) { right = mid; } else { left = mid + 1; } } return left; } // Driver code int main() { vector< int > sectionss = { 8, 11, 18, 20 }; int H = 10; // Function Call cout << minSolvingSpeed(sectionss, H); return 0; } |
Java
//Java Code for the above approach import java.util.*; class Main { // Function to check if all sections can be solved within a given speed and time static boolean canSolveAll(List<Integer> sections, int speed, int h) { int time = 0 ; for ( int section : sections) { // Calculate time required to solve current section at the given speed time += (section - 1 ) / speed + 1 ; // If total time exceeds the given limit, return false if (time > h) { return false ; } } return true ; } // Function to find the minimum solving speed required static int minSolvingSpeed(List<Integer> sections, int h) { int left = 1 ; int right = Collections.max(sections); // Binary search to find the minimum solving speed while (left < right) { int mid = (left + right) / 2 ; if (canSolveAll(sections, mid, h)) { right = mid; } else { left = mid + 1 ; } } return left; } public static void main(String[] args) { List<Integer> sections = Arrays.asList( 8 , 11 , 18 , 20 ); int H = 10 ; // Call the minSolvingSpeed function to find the minimum eating speed required int result = minSolvingSpeed(sections, H); // Print the result System.out.println( "Minimum eating speed required: " + result); } } //This Code is Contributed by chinmaya121221 |
Python
def can_solve_all(sections, speed, h): time = 0 for section in sections: time + = (section - 1 ) / / speed + 1 if time > h: return False return True def min_solving_speed(sections, h): left = 1 right = max (sections) while left < right: mid = (left + right) / / 2 if can_solve_all(sections, mid, h): right = mid else : left = mid + 1 return left def main(): sections = [ 8 , 11 , 18 , 20 ] H = 10 # Function Call print (min_solving_speed(sections, H)) if __name__ = = "__main__" : main() |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static bool CanSolveAll(List< int > sections, int speed, int h) { int time = 0; foreach ( int section in sections) { time += (section - 1) / speed + 1; if (time > h) { return false ; } } return true ; } static int MinSolvingSpeed(List< int > sections, int h) { int left = 1; int right = sections.Max(); while (left < right) { int mid = (left + right) / 2; if (CanSolveAll(sections, mid, h)) { right = mid; } else { left = mid + 1; } } return left; } static void Main( string [] args) { List< int > sections = new List< int > { 8, 11, 18, 20 }; int H = 10; // Function Call Console.WriteLine(MinSolvingSpeed(sections, H)); } } |
Javascript
// JavaScript code for the above approach: function canSolveAll(sections, speed, h) { let time = 0; for (let section of sections) { time += Math.floor((section - 1) / speed) + 1; if (time > h) { return false ; } } return true ; } function minSolvingSpeed(sections, h) { let left = 1; let right = Math.max(...sections); while (left < right) { let mid = Math.floor((left + right) / 2); if (canSolveAll(sections, mid, h)) { right = mid; } else { left = mid + 1; } } return left; } // Driver code let sections = [8, 11, 18, 20]; let H = 10; // Function Call console.log(minSolvingSpeed(sections, H)); |
7
Time Complexity: O(n.logn)
Auxiliary Space: O(1)