Is the Interval Partitioning algorithm (below) optimal if thegreedy strategy is

Question

Is the Interval Partitioning algorithm (below) optimal if thegreedy strategy is the earliest finish time first? Proveor disprove it.

               Sort the intervals by their start times, breaking tiesarbitrarily

               Let I1, I2, …, In denote theintervals in this order

               For j = 1, 2, 3, .., n

                               For each interval Ii that precedes Ij insorted order and overlaps it

                                               Exclude the label of Ii from consideration forIj

                               Endfor

                               If there is any label from {1, 2, …, d} that hasn’tbeen excluded then

                                              Assign a nonexluded label to Ij

                               Else

                                               Leave Ij unlabeled

                               Endif

Explanation / Answer

Optimal solution of interval partioning algorithms greed partis early first. SCHEDULE(a[1...N]) 1. sort a[1...N] by finish time 2. A<-- a[1]      //Scheduledactivity 1 first. 3.prev<--1; 4.for v=2 to N 5.   doif(a[v].start>=a[prev].finish) 6.      thenA<--AUa[v];    prev<--v

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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