Question

3.2 L5 To solve the problem: problem decomposition: we would like to find the requests one by one. Idea 1: select the request with the earliest start time from the requests compatible with the selected ones. Greedy: earliest start time. Candidates: requests compatible with the selected ones. It does not work in the example (a) below: Idea 2: select the request with the smallest duration from the requests compatible with the selected ones. Greedy: smallest duration. Candidates: requests compatible with the selected ones. It does not work in the example (b) below. Idea 3: select the request that overlaps with the least number of requests compatible with the selected ones. Greedy: least overlapping. Candidates: requests compatible with the selected ones. It does not work in the example (C) below. (a) (b) (c) Idea 4 (workable): elect the request that finishes the earliest from those compatible with the selected ones. Greedy: finishes the earliest. Candidates: requests compatible with the selected ones. 1. Question: Consider the interval scheduling problem with a set of requests 1, 2, 3, 4, 5, 6, 7, 8 and their start time and finishing time: (1) = 0, f(1) = 2, s(2) = 0, f(2) = 4, s(3) = 3, f(3) = 6, s(4) = 5, f(4) = 7, s(5) = 8, f(5) = 10, s(6) = 0,f(6) = 11, s(7) = 9, f(7) = 12, s(8)=14, f(8)=15, s(9) = 13, f(9)=16. The interval scheduling problem is to find the maximum subset of the requests that are compatible. Following the algorithm idea for solving interval scheduling problem in 3.2 of L5, write each request selected, in the order, by the algorithm.

Answer 1

Since it has been depicted through examples/figure that idea 1, idea 2 and idea 3 does not work so we will directly utilise idea 4 for solving this question.

For the sake of convenience, let's write the requests in the following ways:-

1. <0, 2>
2. <0, 4>
3. <3, 6>
4. <5, 7>
5. <8, 10>
6. <0, 11>
7. <9, 12>
8. <14, 15>
9. <13, 16>

Now, we will sort the requests in the increasing order of their finish time, so that we can greedily select the requests from the sorted list. After sorting the list, it looks looks as follows:

1. <0, 2> // this request has the earliest finishing time.....
2. <0, 4>
3. <3, 6>
4. <5, 7>
5. <8, 10>
6. <0, 11>
7. <9, 12>
8. <14, 15>
9. <13, 16>

Now, comes the most tricky part, How to select the requests from this sorted list?

1) Selects the first request directly and add it to the new list ans.

2) Select next request from the sorted list, and check if this request's time interval clashes/overlaps with any of the requests in ans then discard that request otherwise add this request into ans.

.We will run step 1 and 2 on our example to clearly demonstrate what is going on actually,

• <0, 2> is selected and added into ans. So our ans = { <0, 2> }
• <0, 4> has a overlapping of interval with requests already present in ans i.e <0, 4> is overlapping with <0, 2>, so <0, 4> must not be included in ans and our ans = { <0, 2> }
• For <3, 6>, it does not clash with <0, 2> so it will add in ans and our ans = { <0, 2> , <3, 6>}
• For <5, 7>, as it clashes with <3, 6> , so it will not be added and our ans = { <0, 2> , <3, 6>}.
• For <8, 10>, as it does not clashes with any request inside ans so it will added to ans and our ans = { <0, 2> , <3, 6>, <8, 10>}.
• For <0, 11>, it clearly clashes with some requests in ans so it should be discarded and our ans = { <0, 2> , <3, 6>, <8, 10>}.
• For <9, 12>, it clearly clashes with <8,10> (present in ans) so must not be included in ans and our ans = { <0, 2> , <3, 6>, <8, 10>}.
• For <14, 15>, no clashes can be found in ans so it will be added in ans and our new ans = { <0, 2> , <3, 6>, <8, 10>, <14, 15>}.
• For last request <13, 16>, it is clashing with <14, 15>(present in ans) so must not be added in ans and our ans = { <0, 2> , <3, 6>, <8, 10>, <14, 15>}

So finally our list ans contains the maximum subset of requests that can be handled with ans = { <0, 2> , <3, 6>, <8, 10>, <14, 15>}. I have run algorithm given in the book written by Thomas H. Cormen so you can refer there for it's proof and all other stuff that you may want.