Minimizing the number of blocks
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(n4) by dynamic programming.
-- joint work with Philippe Baptiste and Marek Chrobak.