Solution: There are also some variants to this problem, like putting m integers to n buckets. The solution to this problem can be based on some heuristics and is called LPT algorithm. Attention: this is a greedy approach which is a sub-optimal solution, not an optimal solution.
- Basically we first sort the job based on their process time.
- Choose the job with the longest process time among the current unprocessed jobs and put it into a machine which has the earliest finish time so far.
- Repeat the above steps until all jobs are assigned.
- The complexity is O(m*logm+m*logn+n).
why m*logn has been added to the complexity ??
ReplyDeletem*logm is for sorting all the jobs based on their process time.
Deletem*logn is for finding a machine which has the earliest finish time. In order to achieve this, we need a min-heap (or priority queue). Each round, we pick the machine that finishes earliest. This operation costs logn. Since there are m jobs, for each job, we need to do such operation. Thus the total is m*logn.
ok i got it .. but i guess you should also include time complexity for building min-heap for n processors which is n*logn ....right????
Deleteif you insert element one by one, the cost of building a heap is (O)nlogn. However, optimal approach takes only (o)n to build a heap. Please see http://en.wikipedia.org/wiki/Binary_heap.
Delete