Consider the following variation on the Interval SchedulingProblem.
You have a processor that can operate 24 hours a day,every day. People
submit requests to run daily jobs on theprocessor. Each such job comes
with a start time and an end time;if the job is accepted to run on the
processor, it must runcontinuously, every day, for the period between
its start and endtimes. (Note that certain hobs can begin before
midnight and endafter midnight; this makes for a type of situation
different fromwhat we saw in the Interval Scheduling Problem).
Given a list of n such jobs, you goal is to accept as
many jobs aspossible (regardless of length), subject to the constraint
that theprocessor can run at most on job at any given point in
time.Provide an algorithm to do this with a running time that
ispolynomial in n. You may assume for simplicity that no two jobshave
the same start or end times.
Example: Consider the following 4 jobs, specified by
(start-time,emd-time) pairs:
(6 P.M., 6 A.M), (9 P.M., 4 A.M.), (3
A.M., 2 P.M.), (1 P.M., 7P.M.).
The optimal solution would be to pick the two jobs (9 P.M., 4A.M.) and
(1 P.M., 7 P.M.), which can be scheduled withoutoverlapping.
Analyze the running time complexity and prove the optimality ofthe
algorithm you provide.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
