  We study the online preemptive scheduling of intervals and jobs (with
restarts). Each interval or job has an arrival time, a deadline, a length and a
weight. The objective is to maximize the total weight of completed intervals or
jobs. While the deterministic case for intervals was settled a long time ago,
the randomized case remains open. In this paper we first give a 2-competitive
randomized algorithm for the case of equal length intervals. The algorithm is
barely random in the sense that it randomly chooses between two deterministic
algorithms at the beginning and then sticks with it thereafter. Then we extend
the algorithm to cover several other cases of interval scheduling including
monotone instances, C-benevolent instances and D-benevolent instances, giving
the same competitive ratio. These algorithms are surprisingly simple but have
the best competitive ratio against all previous (fully or barely) randomized
algorithms. Next we extend the idea to give a 3-competitive algorithm for equal
length jobs. Finally, we prove a lower bound of 2 on the competitive ratio of
all barely random algorithms that choose between two deterministic algorithms
for scheduling equal length intervals (and hence jobs).
