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.