We are given a set of n asynchronous tasks that are to be scheduled. Each task has a given finish time.
We do not allow finish time of one task to overlap the start time of another one. And, there are maximum of 3 tasks could process concurrency.
How do we schedule the tasks to finish them all at the earliest time in javascript ?
Let ‘s see the code bellow. And we have to implement the run function that will do all tasks concurrency.
There are many ways to solve this problem in javascript.
Solution 1:
Take 3 tasks and do it concurrency by using Promise.all
It means, the finish time is the longest time in one of 3 tasks.
Total time: 56s
why does it take 56s to finish ?
Because, by using Promise.all, all tasks will process concurrency, but Promise.all will only resolve all tasks when the longest time task finished.
For example, see this explanation below:
Promise.all ([ task 1, task2, task 3: 2s,4s,6s ]) : resolved after 6s.
Promise.all ([ task4, task5, task6: 8s,10s,12s ]) : resolved after 12s.
Promise.all ([ task7, task8, task9: 14s,16s,18s ]): resolved after 18s.
Promise.all ([ task10 ]): 20s: resolved after 20s.
So, totaltime is 6 + 12 + 18 + 20 = 56s
Solution 2:
Start 3 first tasks, whenever any task complete, resolve it, and start new task in waiting list immediately.
Supposed that there is a result table, and 1 cell in table is 2s. This table below will illustrate the result for solution 2.
Total time is 44s. It ‘s really better than solution 1.
But, I am wondering if it would be the best result for all ?
We could optimize the finish time less than 44s.
Try to sort the array tasks time order by desc, and try it again.
And let ‘s see the result. Total time is only 38s.
The table bellow will explain the result:
We call this solution is one of the greedy algorithms (strategy: the longest time will be finished first).
And 38s is total time to finish all tasks. But, remember that, greedy can’t always resolve the best optimization at all.
These problems are called scheduling activities. In general, it ‘s hard to solve efficiently, and we call it NP-hard problems. Greedy algorithm is one of the solution to solve the NP-hard problems.
Due to the simple nature of time intervals, it is possible to solve them quite efficiently by a simple greedy approach by using longest time strategy.
In conclusion, sorting the tasks time in order the longest time first, and do it concurrency. We could finish all asynchronous in the fastest time. And this bellow is the best optimization code for all.
https://gist.github.com/tranquansp/3983f59630b4c227cbf6eca08767b069
