1753. Doing Homework

Description

中文English

For n people, each of them needs to do m jobs independently.
The i job takes cost[i] time. Since each person's free time is different, the i person has val[i] time, which means that the total time for his jobs will not exceed val[i]. Everyone starts with the first job, then the 2nd, the 3rd... Now, you need to figure out how much time they spend.

1<=n<=100000
1<=m<=100000
1<=val[i]<=100000
1<=cost[i]<=100000

Have you met this question in a real interview?  

Example

Example 1:

Given `cost=[1,2,3,5]`,`val=[6,10,4]`, return `15`.
Input:
[1,2,3,5]
[6,10,4]
Output:
15

Explanation:
The first person can complete the 1st job, the 2nd job, the 3rd job, 1+2+3<=6.
The second person cancomplete the 1st job, the 2nd job, the 3rd job, and cannot complete the 4th job, 1+2+3<=10, 1+2+3+5>10.
The third person can complete  the 1st job, the 2nd job, and cannot complete the 3rd job,  1+2<=4, 1+2+3>4.
1+2+3+1+2+3+1+2=15, returning 15.

Code(Language:C++)

class Solution {
public:
    /**
     * @param cost: the cost
     * @param val: the val
     * @return: the all cost
     */
    long long doingHomework(vector<int> &cost, vector<int> &val) {
        // Write your code here.
        long long res = 0; 
        const int size = cost.size();
        if(size == 0){
            return res; 
        }
        vector<int> prefixSum(size, 0);
        prefixSum[0] = cost[0];
        for(int i = 1; i < size; i++){
            prefixSum[i] = prefixSum[i - 1] + cost[i]; 
        }
        
        for(int i = 0; i < val.size(); i++){
            // search the max num equal or smaller than val[i].
            int target = val[i]; 
            int start = 0;
            int end = size - 1; 
            //int flag = 0; 
            while(start + 1 < end){
                int mid = start + (end - start) / 2; 
                if(prefixSum[mid] <= target){
                    start = mid; 
                }
                else{
                    end = mid; 
                }
            }
            if(prefixSum[end] <= target){
                res += prefixSum[end]; 
            }
            else if(prefixSum[start] <= target){
                res += prefixSum[start]; 
            }
            
        }
        return res; 
    }
};