NOTE:

*** you must also prove that your algorithm is correct and analyze its running time ***

The Montral Jazz Fest is on this summer, and you know what that means: it's time to make some money by selling bootleg recordings! You have a list of the events that are being played at the Jazz Fest, namely: their start times, the length of each event, and also the location at which the event is playing. However, it may be impossible to attend every event in order to make a bootleg recording, so, you will have to hire some accomplices to help you out. Naturally, in order to maximize your profit, you would prefer to figure out the minimum number of people you need to hire in order to cover every single event. Being a computer scientist, you decide to come up with an algorithm to solve the job. Give an efficient algorithm for the following problem. As input, you receive a list of locations L1,..., ..., Lm and a list of events E1, E2, ..., En occuring on a single day, where each event E; is specified by a start time t, an event length li, and the location L that the event occurs at (you may assume that all events are scheduled so that no two overlap at the same location). You also receive a list of integers tij for each pair of locations Li, L; that represents the travel time from location i to location j in minutes. Your algorithm should determine the fewest number of people required to attend all of the events, and output an event schedule for each of the persons