Consider the following variation on the Interval Scheduling Problem. You have a supercomputer that can operate 24 hours a day, every day. People submit requests to run daily jobs on the supercomputer. Each such job request includes a fixed and pre-determined start time and an end time. If a job request is accepted it must run continuously, every day, for the period between the requested start and end times. Jobs can begin before midnight and end after midnight. (This makes for a type of situation different from what we saw in the Interval Scheduling Problem.) The supercomputer can run at most one job at any given point in time; no two jobs can run concurrently.

Given a list of n such job requests, provide an algorithm to accept as many job requests as possible (regardless of their length). Your algorithm should have a running time that is O(n^2). You may assume for simplicity that no two jobs have the same start or end times. Example. Consider the following four jobs, specified by (start-time, end-time) pairs.

(6P.M., 6A.M.), (9P.M., 4A.M.), (3A.M., 2P.M.), (1P.M., 7P.M.). T

he optimal solution would be to pick the two jobs (9P.M.,4A.M.) and (1P.M., 7P.M.), which can be scheduled without overlapping. Please write pseudocode.

Note: You must show your algorithms running time is O(n^2).