backupthreadsSolved.js

// Rewrote my solution from scratch to be more modular
/* Datto is working on creating a backup-time estimator. For simplicity's sake, let's assume that there is only one server completing multiple jobs (i.e. backups) in parallel. Without any parallelization, the ith job takes backupDurationi units of time to be backed up. But if there are n jobs running in parallel, the backup process goes n times slower for each job.

For the ith job you know the value of backupDurationi and the moment startTimesi it was added to the backup queue. Your task is to estimate all the backup completion times. Note that it is impossible to have more than maxThreads threads performing backups in parallel. If there is more than one job waiting to be backed up, the one with the smallest initial backup time is chosen. It's guaranteed that all the jobs are added to the backup queue at different times.

Example

For startTimes = [461620201, 461620202, 461620203],
backupDuration = [2, 2, 2] and maxThreads = 2,
the output should be
backupTimeEstimator(startTimes, backupDuration, maxThreads) = [461620204.0, 461620206.0, 461620207.0].

At moment 461620201 the first job is added to the queue and its backup process starts.

At moment 461620202 the second job is added to the second thread, while the first job is 50% complete in the first thread.

At moment 461620203 another job is added, but both of the threads are busy, so nothing happens (the first job is 75% complete, and second one is 25%).

At moment 461620204 the first job finishes in the first thread, and the third job starts to run. The second job is 50% complete at the moment.

At moment 461620206 the second job finishes, and the third one is 50% complete.

At moment 461620207 the third job finishes its work.

Check out the image below for better understanding.
[image](https://codefightsuserpics.s3.amazonaws.com/tasks/backupTimeEstimator/img/example.jpg?_tm=1490625565918);

For startTimes = [461620201, 461620202, 461620203], backupDuration = [2, 2, 2]
and maxThreads = 3, the output should be
backupTimeEstimator(startTimes, backupDuration, maxThreads) = [461620204.5, 461620206.5, 461620207.0].
Input/Output

[time limit] 4000ms (js)
[input] array.integer startTimes

A sorted array of unique positive integers. The ith element is the time the ith job was added to the backup queue.

Guaranteed constraints:
0 ≤ startTimes.length ≤ 400,
1 ≤ startTimes[i] ≤ 109.

[input] array.integer backupDuration

Array of positive integers of the same size as startTimes. For each valid i backupDuration[i] is the amount of time it takes to back up the ith job if there is only one running thread.

Guaranteed constraints:
backupDuration.length = startTimes.length,
1 ≤ backupDuration[i] ≤ 104.

[input] integer maxThreads

The maximum number of threads that can work in parallel.

Guaranteed constraints:
1 ≤ maxThreads ≤ 45.

[output] array.float

Array of the same length as startTimes, where the ith element is the moment by which the ith job is backed up.
Your output will be considered correct if the absolute error of each output value does not exceed 10-5.

Here's an example test case:
startTimes: [461620415, 461620416, 461620421, 461620424, 461620425, 461620427, 461620434, 461620435, 461620449]
backupDuration: [3, 7, 6, 3, 10, 7, 3, 6, 10]
maxThreads: 5

output: [461620420, 461620435.3333333, 461620445.3333333, 461620437.8333333, 461620464.9166667, 461620458.75, 461620449.4166666, 461620462.25, 461620470]

*/


function backupTimeEstimator(startTimes, backupDuration, maxThreads) {
    let jobsQueue = startTimes.map((job, index) => {
        return {startTime: job, backupDuration: backupDuration[index], index: index};
    });
    
    let jobsWaiting = [];
    let jobsRunning = [];
    let endTimes = Array(startTimes.length).fill(0);
    let currentTime = 0;

    const popQuickestJob = (jobsArr) => {
        // find, remove, and return job with lowest backupDuration from a jobs array.
        if (jobsArr.length === 0 ) {
            return null;
        }
        if (jobsArr.length === 1) {
            return jobsArr.pop();
        } 
        
        let min = jobsArr[0].backupDuration;
        let minIndex = 0;
        jobsArr.forEach((job, index) => {
            if (job.backupDuration < min) {
                min = job.backupDuration;
                minIndex = index;
            }
        });

        return jobsArr.splice(minIndex, 1);
    }
    
    const getClosestJobStartTime = (jobsArr) => {
        // gets the minimum startTime from an array of jobs
        if (jobsArr.length === 0) {
            return Infinity;
        }
        
        return Math.min.apply(null, jobsArr.map((job) => job.startTime));
    }
    
    const getTimeToQuickestJobFinish = (jobsArr) => {
        // gets the minimum time to job finish (considering parallelization, so, i.e. gets timestep)
        if (jobsArr.length === 0) {
            return Infinity;
        } 
        
        return Math.min.apply(null, jobsArr.map((job) => job.backupDuration)) * jobsArr.length;
    }
    
    const updateJobsRunning = (jobsArr, timestep, endTimes) => { 
        // updates the jobs array with the timestep divided amongst each job, and then filters the results to
        // purge the array of any finished jobs and writes the resulting end time in endTimes array.
        // Function doesn't actually mutate jobsArr, just returns the updated one.
        jobsArr.forEach((job) => {
            job.backupDuration -= (timestep / jobsArr.length);
        });
        
        jobsArr = jobsArr.filter((job) => {
            const done = Math.abs(job.backupDuration) <= 0.00001;
            if (done) endTimes[job.index] = currentTime + timestep;
            return !done;
        });
        
        return jobsArr;
    }

    // Three events can happen at any time, with the following precedence (a takes precedence over c) in the case that two events happen at the same time.
    // a) job finishes
    // b) job comes from the jobsWaiting array
    // c) job comes from the jobsQueue array
    // 
    // if a) then choose timestep to job finishing. Update jobs running.
    // if b) job from jobsWaiting. then check if jobsRunning is full. If it is, then choose timestep to job finishing. Update jobs running. If not, then choose timestep to next job. Then update jobs running. Finally, add job to jobsrunning.
    // If c) job from jobsQueue. then check if jobsRunning is full. Regardless, choose timestep to next job start. Then update jobs running. Then, if jobsRunning was full, add job to jobsWaiting, otherwise add it to jobsRunning.
    // Update currentTime = currentTime + timestep in every case.
    // 
    // Edit: I was struggling with this for a while with the caveat below. Came up with two solutions, one worked, the other didn't. Not sure why solution b doesn't work.
    // One caveat: When a job is added to the jobsWaiting queue, we jump forward in time to the next job finish, but this leaves the jobsWaiting to have startTimes before the currentTime. 
    // 
    // solution a) To deal with this, I just consider the fact that when we have a job in jobsWaiting, its start time doesn't matter. The fact that it's in jobsWaiting means we've already past its start point and we should add it now (i.e. at currentTime). And so, whenever we CAN add a jobsWaiting, we just set the timestep to 0 and add it. And so, we just add the check if timestep < 0; timestep = 0; after setting timestep.
    // 
    // solution b) To deal with this, I proposed to add the delay (timestep to next job finished) to each start time in jobsQueue and jobsWaiting. That way, we simulate the real-time addition of jobs to the queue and backup. However, I noticed on the last test case this solution was resulting in small miscalculations, so there must be something wrong with this logic. May come back to this later.
    
    while (jobsQueue.length > 0 || jobsWaiting.length > 0 || jobsRunning.length > 0) {
        // console.log('------------------');        
        // console.log('currentTime: ', currentTime);
        // console.log('jobsRunning: ', jobsRunning);

        let timestep;
        
        const nextJobStartTime = getClosestJobStartTime(jobsQueue.concat(jobsWaiting));
        const nextJobFinishTime = getTimeToQuickestJobFinish(jobsRunning) + currentTime;
        
        // console.log('nextJobStartTime: ', nextJobStartTime);
        // console.log('nextJobFinishTime: ', nextJobFinishTime);
        
        if (nextJobFinishTime <= nextJobStartTime) {
            // option a
            console.log('a');
            timestep = nextJobFinishTime - currentTime;
            if (timestep < 0) timestep = 0;
            jobsRunning = updateJobsRunning(jobsRunning, timestep, endTimes);
        } else {
            
            if (jobsWaiting.length > 0) {
                // option b
                console.log('b');
                if (jobsRunning.length === maxThreads) {
                    console.log('b-1');
                    timestep = nextJobFinishTime - currentTime;
                    if (timestep < 0) timestep = 0;
                    jobsRunning = updateJobsRunning(jobsRunning, timestep, endTimes);
                    
                } else {
                    console.log('b-2');
                    timestep = nextJobStartTime - currentTime;
                    if (timestep < 0) timestep = 0;
                    jobsRunning = updateJobsRunning(jobsRunning, timestep, endTimes);
                    jobsRunning.push(popQuickestJob(jobsWaiting));
                }
            } else {
                // option c
                console.log('c');
                if (jobsRunning.length === maxThreads) {
                    console.log('c-1');
                    timestep = nextJobStartTime - currentTime;
                    if (timestep < 0) timestep = 0;
                    jobsRunning = updateJobsRunning(jobsRunning, timestep, endTimes);
                    jobsWaiting.push(jobsQueue.shift());
                } else {
                    console.log('c-2');
                    timestep = nextJobStartTime - currentTime;
                    if (timestep < 0) timestep = 0;
                    jobsRunning = updateJobsRunning(jobsRunning, timestep, endTimes);
                    jobsRunning.push(jobsQueue.shift());
                }
            }
        }
        
        // console.log('timestep: ', timestep);
        // console.log('jobsRunning: ', jobsRunning);
        // console.log('jobsQueue: ', jobsQueue);        
        // console.log('jobsWaiting: ', jobsWaiting);
        // console.log('endTimes: ', endTimes);
        
        currentTime += timestep;
        // console.log('currentTime: ', currentTime);
    }
    
    return endTimes;
}