def newspapers_split(newspapers_read_times: List[int], num_coworkers: int) -> int:
def workers_are_more_coworker(time):
acc_time, worker_count = 0, 0
for read_time in newspapers_read_times:
if read_time + acc_time > time:
worker_count += 1
acc_time = 0
acc_time += read_time
if acc_time > 0:
worker_count += 1
return worker_count > num_coworkers
low_time, high_time = max(newspapers_read_times), sum(newspapers_read_times)
time = -1
while low_time <= high_time:
mid_time = (low_time + high_time) // 2
if workers_are_more_coworker(mid_time):
low_time = mid_time + 1
else:
high_time = mid_time - 1
time = mid_time
return time
public static boolean isValid(List<Integer> newspapersReadTimes, int numCoworkers, int minimumTime){
int CoWorkerCount = 1;
int currTime = 0;
for(int i = 0; i < newspapersReadTimes.size(); i++){
// calculating reading time by coworker
currTime += newspapersReadTimes.get(i);
// check whether coworker reading time more than expecdted minimum time
if(currTime > minimumTime){
CoWorkerCount++;
currTime = newspapersReadTimes.get(i);
}
// check if actual coworkers more than given coworkers
if(CoWorkerCount > numCoworkers){
return false;
}
}
return true;
}
public static int newspapersSplit(List<Integer> newspapersReadTimes, int numCoworkers) {
int minPossibleTimeToRead = Integer.MIN_VALUE;
int maxPossibleTimeToRead = 0;
int time = -1;
int len = newspapersReadTimes.size();
// find min and max time range for reading newspapers by any coworker
for(int i = 0 ; i < len ; i++){
maxPossibleTimeToRead += newspapersReadTimes.get(i);
minPossibleTimeToRead = Math.max(minPossibleTimeToRead, newspapersReadTimes.get(i));
}
while(minPossibleTimeToRead <= maxPossibleTimeToRead){
int mid = minPossibleTimeToRead + (maxPossibleTimeToRead - minPossibleTimeToRead) / 2;
if(isValid(newspapersReadTimes, numCoworkers, mid) == true){
time = mid;
maxPossibleTimeToRead = mid - 1;
}else{
minPossibleTimeToRead = mid + 1;
}
}
return time;
}
Simple crisp solution in Java passing all test cases.
I did it the other way. It is much simpler to understand.
from typing import List
def canRead(newspaper_read_times: List[int], min_time_needed:int, num_coworker:int) -> bool:
worker_needed = 1
min_time = min_time_needed
for time in newspaper_read_times:
if min_time - time < 0:
worker_needed +=1
min_time = min_time_needed
min_time = min_time - time
return worker_needed <= num_coworker
def newspapers_split(newspapers_read_times: List[int], num_coworkers: int) -> int:
left, right = max(newspapers_read_times), sum(newspapers_read_times)
ans = right
while left <=right:
mid = (left + right) // 2
if canRead(newspapers_read_times, mid, num_coworkers):
right = mid -1
ans = min(mid, ans)
else:
left = mid + 1
return ans
if __name__ == '__main__':
newspapers_read_times = [int(x) for x in input().split()]
num_coworkers = int(input())
res = newspapers_split(newspapers_read_times, num_coworkers)
print(res)
can somebody explain me why we need this condition at line 13 on python solution:
13 if time != 0:
14 num_workers += 1
My understanding is that this condition will always evaluate to true, as we add read_time to time just before it, am I right?
The solution doesnât work for the input [1,2,4,7,8 ] k =2. it keeps giving 14
why is low = newsPapersReadTimes.Max() ? should it is newsPapersReadTimes.Min()?
Hey there
Input: newspapers_read_times = [7,2,5,10,8], num_coworkers = 2
Answer is 18.
I wonder, why it canât be 17? So we assign the first newspaper to the first coworker (7), then we assign two newspapers with 2 and 5 to the second coworker (7), then we assign newspaper 10 to the first coworker again, and then we assign one that left with 8 to the second. So the first coworker will spend 17 instead of 18.
Or maybe I misread the description and we cannot go back and forth with task assignment?
Can someone explain the naive solution to this problem?
What would the time complexity be in a naive/brute force solution?
I was wondering the same thing as you. I think a found an answer why. To give an example, you have an array of length n and the minimum number of people who can read all the newspapers given the problem setup is 4. Each worker cannot take more than 15 minutes. The last newspaper that each worker reads is marked by the times arr[i1], arr[i2], arr[i3], arr[i4]. i4=arr.length-1. Now each worker reads as many consecutive papers as possible without going over the 15 min limit. So how do we know that given different indices j1, j2 we wouldnât get a better solution: only needing 3 workers? Well letâs see. The first index j1 must be <=i1, because if itâs not, the first reader goes over the 15 minute limit. Now the second index j2 must be <=i2, because if itâs not, the second reader goes over the 15 minute limit. But if we only needed 3 workers, the third index j3 would be arr.length-1. Since j3>i3, and our third worker started no later than j2, then they must have already gone over the limit since they went past i3. But that canât happen. At the very least, we need j3<=i3 and j4=i4. So we still have 4 workers. Now just generalize this idea to other inputs.
From the problem statement:
Additionally, the newspapers came in a particular order, and you must not disarrange the original ordering when distributing the newspapers. In other words, you cannot pick and choose newspapers randomly from the whole pile to assign to a co-worker, but rather you must take a subsection of consecutive newspapers from the whole pile.
Youâre proposing splitting the newspapers up in some smart way, but you have to assign a subsection of consecutive newspapers to a co-worker. And once youâve assigned newspapers to a co-worker and moved on to another co-worker, you may no longer assign newspapers to the first.
Going back and forth with task assignment is no different than cherry-picking newspapers and assigning them to co-workers.
This is a wonderful problem that illustrates an important lesson (which I feel could be a mini-pattern in itself): sometimes you use your binary search not on your inputs, but on a range of possible outputs. This is a general enough rule that, I think, should be mentioned explicitly.
1 Like
There seems to me to be a nuance in this solution rooted in the statement âIf a given time t is feasible for num_coworkers to finish all the newspapers, then any time greater than t will also be feasible. This is because if coworkers can complete reading in a shorter amount of time, they can obviously also complete it if given more time.â The actual implementation of the feasible function is not checking for a solution at exactly an amount of time, but rather that a greedy allocation of papers does not violate the time limit. It turns out that the greedy allocation is really the only way given the constraints in the way papers can be allocated. The first coworker is given papers until giving it one more would violate the time limit being tested. Giving that coworker fewer papers would only make the problem worse for all subsequent coworkers. That applies for each subsequent coworker.
Thanks !! this comment helped me understand the solution. I was very puzzled with the given explanation.
IMO This one definitely needed a little more explanation up-front of how binary search can be applied, namely that even with non-monotonic, unsorted data, you can still define a monotonic function that provides a binary-searchable âviewâ of the data. I spent a good amount of time trying to treat this as an optimization or scheduling problem, and finding the best solution of all possible permutations for distributing the workload and worrying about which ones are assigned the remainder etc. In hindsight, of course, I see that the proposed solution here is a much simpler one - I just think itâd be good to provide more material up front to make this sort of approach more obvious. The speedruns should be when we really test ourselves, problems in the study sections IMO should not be so ambiguous.