Problem Statement
You work at a popular thrift shop in Los Angeles where people donate various clothing items for the goodwill of the community. One day, you receive a large shipment of donations with multiple boxes. Each box contains a different number of clothing items. Your job at the store is to sort through these boxes and display them before your shift ends that day.
You have n hours left on your shift to end from the time you start sorting through these boxes. When you start sorting through one box and displaying them, should you finish your work before that hour ends, you take a coffee break until the next hour to break open the next box of clothing.
Given the donations array which logs the number of clothing items in each box, find a minimum rate of sorting k (in number of clothing items per hour) to sort all the items and display them before your shift ends.
Input Format
The first line of input consists of one integer t, which denotes the number of test cases.
Each test case has the following input:
- First line: two space-separated integers n and length where length denotes the size of the donations array.
- Second line: length number of space-separated integers denoting the donations array.
Constraints
1 ≤ t ≤ 103
1 ≤ length ≤ 104
length ≤ n ≤ 109
1 ≤ donationsi ≤ 107
Output Format
For each test case, output one integer k denoting the smallest rate of sorting and displaying of the clothing items. Your code should run in a small amount of time even for big test cases.
Sample Input 1
Input:
2
7 5
4 3 6 8 9
5 3
23 19 15
Output:
6
23
Explanation
For the first testcase, you start sorting through the boxes. Let's say you choose a rate of sorting of the value 6 number of clothing items per hour. For the:
- First box: you finish early and take a break
- Second box: you finish early and take a break
- Third box: you finish just in time
- Fourth box: you will need 2 hours to sort and display the clothing items
- Fifth box: you will need 2 hours to sort and display the clothing items
In total, you finish the sorting in 1+1+1+2+2=7 hours which is before the time your shift ends at. If you choose any other value lesser than 6 as the sorting rate, let's say 5, you will finish in 9 hours, hence not within your shift time.
Similarly, for the second testcase, 23 is the smallest rate of sorting and displaying of clothing items.
Solution
test_cases = int(input())
for _ in range(test_cases):
# Read remaining hours and number of boxes
remaining_hours, num_boxes = map(int, input().split())
# Read the number of clothes in each box
clothes_per_box = list(map(int, input().split()))
# Calculate the total number of clothes
total_clothes = sum(clothes_per_box)
# Initialize binary search bounds
min_rate = 1
max_rate = total_clothes
sorting_rate = max_rate
# Binary search to find the minimum sorting rate
while min_rate <= max_rate:
mid_rate = (min_rate + max_rate) // 2
# Calculate the time taken at the current mid_rate
time_taken = sum((clothes + mid_rate - 1) // mid_rate for clothes in clothes_per_box)
# Check if the time taken is within the remaining hours
if time_taken <= remaining_hours:
sorting_rate = mid_rate # Update the optimal sorting rate
max_rate = mid_rate - 1 # Search in the lower half
else:
min_rate = mid_rate + 1 # Search in the upper half
# Print the optimal sorting rate for the current test case
print(sorting_rate)
Sample Solution Provided by Instructor
import math
def thriftingClothes(donations, n):
# 'l' is initialized to 1, representing the minimum possible value of 'k'.
# 'r' is initialized to the maximum value in the 'donations' list, representing the maximum possible value of 'k'.
l, r = 1, max(donations)
# 'k' is initialized to 'r', as a starting guess for the maximum size of a group of clothes.
k = r
# Start a binary search to find the optimal value of 'k'.
while l <= r:
# 'mid' is the middle value between 'l' and 'r', representing a possible size for the group of clothes.
mid = (l + r) // 2
# 'totalTime' will accumulate the total time needed to process all donations, given the current 'mid' value.
totalTime = 0
# Calculate the total time needed for each donation with the current 'mid' value.
for clothes in donations:
# 'math.ceil(float(clothes) / mid)' calculates how many units of time it takes to process
# 'clothes' items if each unit can process 'mid' items. This ensures we round up to the nearest whole unit.
totalTime += math.ceil(float(clothes) / mid)
# If the total time is less than or equal to 'n', it means the current 'mid' value is a valid candidate for 'k'.
if totalTime <= n:
# Update 'k' to the current 'mid' value, since it satisfies the condition.
k = mid
# Move the search range to the left (to find a potentially smaller valid 'k').
r = mid - 1
else:
# If the total time exceeds 'n', we need a larger 'mid' value (i.e., we move the search range to the right).
l = mid + 1
# After exiting the loop, 'k' will contain the optimal value that meets the condition.
return k
if __name__ == '__main__':
# Read the number of test cases.
tt = int(input())
# Loop through each test case.
for i in range(tt):
# Read two integers: 'n' and 'length'.
# 'n' is the maximum total time allowed to process all donations.
# 'length' is the number of donation piles (unused in the function).
n, length = [int(x) for x in input().split()]
# Read the list of donations, which contains the number of clothes in each donation pile.
donations = [int(x) for x in input().split()]
# Call the 'thriftingClothes' function with the donations and the allowed time 'n', and print the result.
print(thriftingClothes(donations, n))