5. (20 points) You just moved to KAUST and plan to attend the orientation sessio

Question

5. (20 points) You just moved to KAUST and plan to attend the orientation sessions. The orientation consists of n sessions. Each session j is described by a triplet of integers (Si, D, Fi), where S indicates the session start time, D represents the duration of the session and F indicates the session finish time. You would like to attend as many sessions as possible. Note that sessions may be overlapping and you can?t attend a session after it is already started and you can?t leave a session before it finishes. Design an O(n log n) greedy algorithm that will allow you to do so and prove that your algorithm is correct.

Explanation / Answer

Assume the algorithm runs and declares m to be the minimum number of machines needed. We must show that m are really needed.

    Consider the step when the algorithm increases m to its final value and assume the task under consideration is i.
    At this point the current task conflicts with one (or more) task(s) in each of the m-1 machines currently used.
    But all these tasks have start time no later than si since the tasks were processed in order of their start time.
    Since they conflict with i, they each have finishing time after si.
    Hence they all conflict with each other as well (consider time si).
    Hence we really do need m machines.

Complexity

The book asserts that it is easy to see that the algorithm runs in time O(NlogN), but I don't think this is so easy. It is easy to see O(N2).

    The while loop has n iterations.
    You just need to compare the current task with all previous tasks, which shows that the iteration is O(N) and the algorithm is O(N2).
    To get O(log(N)) for each iteration, keep the machines in a heap using as key the latest finishing time assigned to that machine. This tells you when that machine will be free (remember that all tasks assigned so far start no later than si, the current job's start time).
    Check the min element of the tree. If it is free at si, then it is free forever starting at si. We
        Remove the machine from the heap (removeMin).
        Assign the current job to the removed machine.
        Now this machine is free at fi and we re-insert it into the heap.
    If it is not free at si, then no machine is free at si so
        Increase m generating a new machine.
        Assign i to the new machine m
        Insert machine m (which has key fi) into the heap.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.