# 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^{4}) by dynamic programming.
-- joint work with Philippe Baptiste and Marek Chrobak.