Interval scheduling

Several algorithms, that may look promising at first sight, actually do not find the optimal solution:[2]

• Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests.
• Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal.

The following greedy algorithm, called Earliest deadline first scheduling, does find the optimal solution for unweighted single-interval scheduling:

1. Select the interval, x, with the earliest finishing time.
2. Remove x, and all intervals intersecting x, from the set of candidate intervals.
3. Repeat until the set of candidate intervals is empty.

Whenever we select an interval at step 1, we may have to remove many intervals in step 2. However, all these intervals necessarily cross the finishing time of x, and thus they all cross each other. Hence, at most 1 of these intervals can be in the optimal solution. Hence, for every interval in the optimal solution, there is an interval in the greedy solution. This proves that the greedy algorithm indeed finds an optimal solution.

A more formal explanation is given by a Charging argument.

The greedy algorithm can be executed in time O(n log n), where n is the number of tasks, using a preprocessing step in which the tasks are sorted by their finishing times.

Problems involving weighted interval scheduling are equivalent to finding a maximum-weight independent set in an interval graph. Such problems can be solved in polynomial time.[3]

Assuming the vectors are sorted from earliest to latest finish time, the following pseudocode determines the maximum weight of a single-interval schedule in Θ(n) time:

// The vectors are already sorted from earliest to latest finish time.
int v[numOfVectors + 1]; // list of interval vectors
int w[numOfVectors + 1]; // w[j] is the weight for v[j].
int p[numOfVectors + 1]; // p[j] is the # of vectors that end before v[j] begins.
int M[numOfVectors + 1]; 
int finalSchedule[];

// v[0] does not exist, and the first interval vector is assigned to v[1].
w[0] = 0; p[0] = 0; M[0] = 0;

// The following code determines the value of M for each vector.
// The maximum weight of the schedule is equal to M[numOfVectors].
for (int i = 1; i < numOfVectors + 1; i++) {
    M[i] = max(w[i] + M[p[i]], M[i - 1]);
}

// Function to construct the optimal schedule
schedule (j) {
    if (j == 0) { return; }
    else if (w[j] + M[p[j]] >= M[j - 1]){
        prepend(v[j], finalSchedule); // prepends v[j] to schedule.
        schedule(p[j]);
    } else { schedule(j - 1); }
}

[4]

If we have the following 9 vectors sorted by finish time, with the weights above each corresponding interval, we can determine which of these vectors are included in our maximum weight schedule which only contains a subset of the following vectors.

Here, we input our final vector (where j=9 in this example) into our schedule function from the code block above. We perform the actions in the table below until j is set to 0, at which point, we only include into our final schedule the encountered intervals which met the ${\textstyle w[j]+M[p[j]]\geq M[j-1]}$ requirement. This final schedule is the schedule with the maximum weight.

j	Calculation	${\textstyle w[j]+M[p[j]]\geq M[j-1]}$ (i.e. This vector is included in the final schedule)	Set j to
9	${\displaystyle {\begin{aligned}&w[j]+M[p[j]]=w[9]+M[p[9]]=5+M[6]=5+16=21\\&M[j-1]=M[9-1]=M[8]=20\end{aligned}}}$	True	j=p[j]=p[9]=6
6	${\displaystyle {\begin{aligned}&w[j]+M[p[j]]=w[6]+M[p[6]]=5+M[4]=5+11=16\\&M[j-1]=M[6-1]=M[5]=11\end{aligned}}}$	True	j=p[j]=p[6]=4
4	${\displaystyle {\begin{aligned}&w[j]+M[p[j]]=w[4]+M[p[4]]=3+M[1]=3+5=8\\&M[j-1]=M[4-1]=M[3]=11\\\end{aligned}}}$	False	j=j-1=4-1=3
3	${\displaystyle {\begin{aligned}&w[j]+M[p[j]]=w[3]+M[p[3]]=6+M[1]=6+5=11\\&M[j-1]=M[3-1]=M[2]=5\end{aligned}}}$	True	j=p[j]=p[3]=1
1	${\displaystyle {\begin{aligned}&w[j]+M[p[j]]=w[1]+M[p[1]]=5+M[0]=5+0=5\\&M[j-1]=M[1-1]=M[0]=0\end{aligned}}}$	True	j=p[j]=p[1]=0

GISDPk is NP-complete when ${\displaystyle k\geq 3}$,[5] even when all intervals have the same length.[6] This can be shown by a reduction from the following version of the Boolean satisfiability problem, which was shown [7] to be NP-complete likewise to the unrestricted version.

Let ${\displaystyle X=\{x_{1},x_{2},\dots ,x_{p}\}}$ be a set of Boolean variables. Let ${\displaystyle C=\{c_{1},c_{2},\dots ,c_{q}\}}$ be a set of clauses over X such that (1) each clause in C has at most three literals and (2) each variable is restricted to appear once or twice positively and once negatively overall in C. Decide whether there is an assignment to variables of X such that each clause in C has at least one true literal.

Given an instance of this satisfiability problem, construct the following instance of GISDP. All intervals have a length of 3, so it is sufficient to represent each interval by its starting time:

• For every variable ${\displaystyle x_{i}}$ (for i=1,...,p), create a group with two intervals: one starting at ${\displaystyle 50i-10}$ (representing the assignment ${\displaystyle x_{i}=\mathrm {false} }$) and another starting at ${\displaystyle 50i+10}$ (representing the assignment ${\displaystyle x_{i}=\mathrm {true} }$).
• For every clause ${\displaystyle c_{j}}$ (for j=1,...,q), create a group with the following intervals:
  • For every variable ${\displaystyle x_{i}}$ that appears positively for the first time in C — an interval starting at ${\displaystyle 50i-12}$.
  • For every variable ${\displaystyle x_{i}}$ that appears positively for the second time in C — an interval starting at ${\displaystyle 50i-8}$. Note that both these intervals intersect the interval ${\displaystyle 50i-10}$, associated with ${\displaystyle x_{i}=\mathrm {false} }$.
  • For every variable ${\displaystyle x_{i}}$ that appears negatively - an interval starting at ${\displaystyle 50i+8}$. This interval intersects the interval ${\displaystyle 50i+10}$ associated with ${\displaystyle x_{i}={\text{true}}}$.

Note that there is no overlap between intervals in groups associated with different clauses. This is ensured since a variable appears at most twice positively and once negatively.

The constructed GISDP has a feasible solution (i.e. a scheduling in which each group is represented), if and only if the given set of boolean clauses has a satisfying assignment. Hence GISDP3 is NP-complete, and so is GISDPk for every ${\displaystyle k\geq 3}$.

GISDP2 can be solved at polynomial time by the following reduction to the 2-satisfiability problem:[6]

• For every group i create two variables, representing its two intervals: ${\displaystyle x_{i}}$ and ${\displaystyle y_{i}}$.
• For every group i, create the clauses: ${\displaystyle x_{i}\cup y_{i}}$ and ${\displaystyle \neg {x_{i}}\cup \neg {y_{i}}}$, which represent the assertion that exactly one of these two intervals should be selected.
• For every two intersecting intervals (i.e. ${\displaystyle x_{i}}$ and ${\displaystyle y_{j}}$) create the clause: ${\displaystyle \neg {x_{i}}\cup \neg {y_{j}}}$, which represent the assertion that at most one of these two intervals should be selected.

This construction contains at most O(n²) clauses (one for each intersection between intervals, plus two for each group). Each clause contains 2 literals. The satisfiability of such formulas can be decided in time linear in the number of clauses (see 2-SAT). Therefore, the GISDP2 can be solved in polynomial time.

GISMPk is NP-complete even when ${\displaystyle k\geq 2}$.[8]

Moreover, GISMPk is MaxSNP-complete, i.e., it does not have a PTAS unless P=NP. This can be proved by showing an approximation-preserving reduction from MAX 3-SAT-3 to GISMP2.[8]

The following greedy algorithm finds a solution that contains at least 1/2 of the optimal number of intervals:[8]

1. Select the interval, x, with the earliest finishing time.
2. Remove x, and all intervals intersecting x, and all intervals in the same group of x, from the set of candidate intervals.
3. Continue until the set of candidate intervals is empty.

A formal explanation is given by a Charging argument.

The approximation factor of 2 is tight. For example, in the following instance of GISMP2:

• Group #1: {[0..2], [4..6]}
• Group #2: {[1..3]}

The greedy algorithm selects only 1 interval [0..2] from group #1, while an optimal scheduling is to select [1..3] from group #2 and then [4..6] from group #1.

A more general approximation algorithm attains a 2-factor approximation for the weighted case.[3]

Using the technique of Linear programming relaxation, it is possible to approximate the optimal scheduling with slightly better approximation factors. The approximation ratio of the first such algorithm is asymptotically 2 when k is large, but when k=2 the algorithm achieves an approximation ratio of 5/3.[8] The approximation factor for arbitrary k was later improved to 1.582.[9]