Homework 3

---

Circular Interval Scheduling

Textbook Exercise 17 in Chapter 4. In your answer, write:

1. the pseudocode of an executable algorithm
2. the analysis of the running time complexity
3. proof of the optimality of the algorithm

Your algorithm, CircIntvlSched, can call IntvlSched shown below if and as needed. Consider the implementation of IntvlSched that has the running time complexity O(n logn). The proof of optimality is trivial from the optimality of IntvlSched; consider the optimality of IntvlSched already proven.

Pseudocode

See Figure 2 below(may be on another page). Created using the LaTeX packages algorithm, algpseudocode, and amsmath.

Time Complexity

Let’s let $n$ be a number of jobs.

For each anchor $j$ we have (with $n$ choices), we test $j$ with job $k$, this is $O(n)$ as the overlap tests are only $O(1)$

Mapping the compatibility list is $O(n)$.

Calling IntvlSched on LinearList has worst case possibility of $O(n)$, and we know that IntvlShed is $O(n\log n)$.

Given that every anchor iteration is $O(n+n\log n)$, and since we repeat for n anchors this is $O(n^2\log n)$.

Space complexity is $O(n)$ overall, for the linear list.

Proof of Optimality

Lets say OP is the optimal set for mutually non-overlapping jobs on this circular schedule. If we assume $OP=\varnothing$ then algorithm returns $\varnothing$ and it is guaranteed correct.

For alternative case, we will consider when $anchor=a$. Using construction:

1. remove all other jobs that overlap on $a$ (only those that can be scheduled with $a$ remain)
2. make a cut on the circular schedule, $cut=e[a]$, then map remaining jobs into the linear 24 hour window. We cut at the end of $a$, so no remaining jobs are on the cut.
3. now, our optimal schedule $OP$(without a) has a mapping to a set of linear intervals with no overlap.

Given that IntvlSched is optimal for linear scheduling, we know that it returns a max size set for all sets of compatible jobs that do not overlap over $a$.

This means that the return set on this anchor is at least $|O{P}_a+1|=|OP|$, meaning the algorithm will find a schedule with a size that is at least the size of $OP$. And given that $OP$ is optimal, so is the algorithm schedule.

---

Interval Partitioning: Greedy Strategies

Consider the IntvlPart greedy algorithm with the earliest start time first strategy we discussed in class (pseudocode shown below), and consider the following three alternative greedy strategies:

1. Earliest finish time first – consider lectures in ascending order of finish time f(j)
2. Shortest interval first – consider lectures in ascending order of interval length, f(j) – s(j)
3. Fewest conflicts first – for each lecture, count the number of conflicting lectures; then, consider lectures in ascending order of the number of conflicts.

For each of these three greedy strategies, either prove or disprove if it is an optimal greedy strategy. If you want to prove it, use a proof technique of your choice (e.g., induction, contradiction, construction) and name the used proof technique at the beginning of the proof. If you want to disprove it, it suffices to provide a counterexample and state what the greedy strategy finds as a solution and what a true optimal solution is. For simplicity, your counterexample should contain as few lectures as you can find. Hint: remember we used a structural bound called “depth”, which denotes the largest number of intervals overlapping at any time.

Earliest Finish time First

Seek to disprove using counterexample:

First, we look at the given lectures $s(1)\dots s(n)$, in this case, $A\dots D$:

$$\begin{array}{r}A=\{0,1\}\\ B=\{0,2\}\\ C=\{1,4\}\\ D=\{2,3\}\end{array}$$

The depth is 2 given max overlapping intervals, meaning that any optimal choice will use 2.

We then order by finish time, so $A(0,1),B(0,2),D(2,3),C(1,4)$

Then run greedy partitioning:

• $A(0,1)\to Roo{m}_1\to lastFin(Roo{m}_1)=1$
• $B(0,2)\to 0<1:Roo{m}_2\to lastFin(Roo{m}_2)=2$
• $D(2,3)\to 2\ge 2(\text{lastFin is Room1})\to D.start=2\ge Roo{m}_1.lastFin=1\to lastfin(Roo{m}_1)=3$
• $C(1,4)\to lastFin(Roo{m}_2)(\text{meaning cant used as C.start=1})\to createRoo{m}_3$

This finish time order uses 3 rooms and not 2, so this is not optimal.

Shortest Interval First

Seek to disprove using counterexample:

Given two Lectures $X=\{0,2\}$ and $Y=\{2,3\}$, length 2 and 1 respectively, and their depth being 1 so optimal path needs 1 room.

Then we order by interval length, so $Y$ then $X$.

Run greedy partitioning:

• $Y\{2,3\}\to Roo{m}_1\to lastFin=3$
• $X\{0,2\}\to X.start=0<lastFin(Roo{m}_1)=3\to ca{n}^{\prime }tuseroo{m}_1\to Roo{m}_2$

This yields 2 rooms with greedy partitioning, when the optimal is 1, and is thus not optimal.

Fewest Conflicts First

Seek to disprove using counterexample:

Given $A,B,C$:

$$\begin{array}{r}A=\{0,1\}\\ B=\{0,2\}\\ C=\{2,3\}\end{array}$$

And the conflicts that come with it:

• $A\to conflict\to B\to conflicts(A)=1$
• $B\to conflict\to A\to conflicts(B)=1$
• $C\to conflict\to \varnothing \to conflicts(C)=o$

Resulting in a depth of 2 as B/A overlap. Optimal is 2 rooms.

Run greedy partitioning:

• $C\{2,3\}\to roo{m}_1\to lastFin=3$
• $A\{0,1\}\to A.start=0<lastFin(Roo{m}_1)=3\to ca{n}^{\prime }troo{m}_1\to Roo{m}_{2}lastFin=1$
• $B\{0,2\}\to lastFin(Roo{m}_2)=1,B.start=0<1\to ca{n}^{\prime }troo{m}_2\to lastFin(Roo{m}_1)=3>0\to cantroo{m}_1\to Roo{m}_3$

This yields 3 rooms when the optimal is 2, therefore fewest conflicts is not an optimal algorithm.