  In online interval scheduling, the input is an online sequence of intervals,
and the goal is to accept a maximum number of non-overlapping intervals. In the
more general disjoint path allocation problem, the input is a sequence of
requests, each involving a pair of vertices of a known graph, and the goal is
to accept a maximum number of requests forming edge-disjoint paths between
accepted pairs. These problems have been studied under extreme settings without
information about the input or with error-free advice. We study an intermediate
setting with a potentially erroneous prediction that specifies the set of
intervals/requests forming the input sequence. For both problems, we provide
tight upper and lower bounds on the competitive ratios of online algorithms as
a function of the prediction error. For disjoint path allocation, our results
rule out the possibility of obtaining a better competitive ratio than that of a
simple algorithm that fully trusts predictions, whereas, for interval
scheduling, we develop a superior algorithm. We also present asymptotically
tight trade-offs between consistency (competitive ratio with error-free
predictions) and robustness (competitive ratio with adversarial predictions) of
interval scheduling algorithms. Finally, we provide experimental results on
real-world scheduling workloads that confirm our theoretical analysis.
