Given_n_books and the_i_th book hasA[i]pages. You are given_k_people to copy the_n_books.
_n_books list in a row and each person can claim a continous range of the_n_books. For example one copier can copy the books from_i_th to_j_th continously, but he can not copy the 1st book, 2nd book and 4th book (without 3rd book).
They start copying books at the same time and they all cost 1 minute to copy 1 page of a book. What's the best strategy to assign books so that the slowest copier can finish at earliest time?
Have you met this question in a real interview?
Yes
Example
Given array A =[3,2,4], k =2.
Return5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )
line 37 not w[1][n] , should be w[1][i]
class Solution {
public:
/\*\*
\* @param pages: a vector of integers
\* @param k: an integer
\* @return: an integer
\*/
int copyBooks\(vector<int> &pages, int k\) {
// write your code here
if \(pages.empty\(\)\) {
return 0;
}
int start = numeric\_limits<int>::min\(\);
int end = 0;
for \(int page : pages\) {
end += page;
if \(page > start\) {
start = page;
}
}
while \(start + 1 < end\) {
int mid = \(end - start\) / 2 + start;
if \(PersonNeeded\(pages, mid\) <= k\) {
end = mid;
} else {
start = mid;
}
}
if \(PersonNeeded\(pages, start\) <= k\) {
return start;
}
return end;
}
int PersonNeeded\(vector<int>& pages, int limit\) {
int person = 1;
int sum = 0;
for \(int page : pages\) {
if \(sum + page > limit\) {
sum = 0;
++person;
}
sum += page;
}
return person;
}
};