  In the problem of online unweighted interval selection, the objective is to
maximize the number of non-conflicting intervals accepted by the algorithm. In
the conventional online model of irrevocable decisions, there is an Omega(n)
lower bound on the competitive ratio, even for randomized algorithms [Bachmann
et al. 2013]. In a line of work that allows for revocable acceptances, [Faigle
and Nawijn 1995] gave a greedy 1-competitive (i.e. optimal) algorithm in the
real-time model, where intervals arrive in order of non-decreasing starting
times. The natural extension of their algorithm in the adversarial (any-order)
model is 2k-competitive [Borodin and Karavasilis 2023], when there are at most
k different interval lengths, and that is optimal for all deterministic, and
memoryless randomized algorithms. We study this problem in the random-order
model, where the adversary chooses the instance, but the online sequence is a
uniformly random permutation of the items. We consider the same algorithm that
is optimal in the cases of the real-time and any-order models, and give an
upper bound of 2.5 on the competitive ratio under random-order arrivals.
  We also show how to utilize random-order arrivals to extract a random bit
with a worst case bias of 2/3, when there are at least two distinct item types.
We use this bit to derandomize the barely random algorithm of [Fung et al.
2014] and get a deterministic 3-competitive algorithm for single-length
interval selection with arbitrary weights.
