Minimizing the number of blocks
or 1|r_i;p_i=1;L=1|E

In this problem we are given n jobs of unit processing time, each comes with a release time and a deadline, time which can be changed on this applet by dragging the mouse. The goal is to produce a schedule which minimizes the number of blocks in the schedule, where a block is a maximal interval in which is the machine is not idle.

This problem can be solved in time O(n⁴) by dynamic programming. -- joint work with Philippe Baptiste and Marek Chrobak.

Minimizing the number of blocks or 1|ri;pi=1;L=1|E

Minimizing the number of blocks
or 1|r_i;p_i=1;L=1|E