Consider the following very simple scheduling problem. You have a resource$$ it may be a lecture room, a

supercomputer, or an electron microscope$$and many people request to use the resource for periods of time.

A request takes the form: Can I reserve the resource starting at time s$,$ until time f$?$ We will assume that

the resource can be used by at most one person at a time. A scheduler wants to accept a subset of these

requests, rejecting all others, so that the accepted requests do not overlap in time. The goal is to maximize

the number of requests accepted.

More formally, there will be n requests labeled $1,...,$ n$,$ with each request i specifying a start time si and

a finish time fi$.$ Naturally, we have si $<$ fi for all i$.$ Two requests i and j are compatible if the requested

intervals do not overlaps: that is$,$ either request i is for an earlier time interval then request j $($fi $<=$ sj $)$ or

request i is for a later time than request j $($fj $<=$ si$).$ We'll say more general that a subset of requests A of

requests is compatible if all pairs of request i$,$ j in A$,$ i $=$ j are compatible. The goal is to select a compatible

subsets of requests of maximum possible size.

An example

$1$