Question

Suppose you’ve taken a part-time job where you drive sales executives of a company to client sites. Each trip starts and ends at the company’s headquarters. A sales executive specifies a trip by its start and finish times. A trip is specified by a start time s and a finish time f. The start time is when you leave the headquarters for a client site; the finish time is when you get back to the headquarters from the client’s site. In particular, you can drive for the trip[s,f] and then the trip[s′,f′] if and only if f≤s′.

Consider a day in your job. At the beginning of the day, the executives have already requested their trips and there’s n of them:(s1,f1),(s2,f2),...,(sn, fn). For some reason, you’re the only driver or the day so you can’t honor all these requests. Some of the executives will just have to take Uber or Lyft. In addition,you’re paid according to the number of trips you complete. How should you choose which trips to drive?

a. Here’s one possibility–pick the trips according to their length; the shorter they are, the better. It seems smart because shorter trips free you up so you can drive for slightly longer trips.

b. Design a different greedy algorithm that takes(s1,f1),(s2,f2),...,(sn, fn) as input and outputs a subset of these trips that you can drive in a day so that the number of trips is as large as possible. What is the running time of your algorithm?

c. Briefly, argue that your algorithm is correct.

Answer 1

Part A>

Picking up trips according the length might seem to be a good idea because choosing shorter jobs leads to selecting more trips. But actually there's a flaw in this solution. Suppose the start time of the shortest trip is the at the end of the time. This means that choosing this approach might result in selecting less number of trips.

Consider the following trips(start time,end time):

(4,9) ; ( 5, 13) ; (10, 15); (11,12)

Here according to selection of shortest jobs first, we select the 4th trip. and after than there is no trip for which  f≤s′. But if we have selected (4,9) and (10,15), we would have completed 2 trips.

Hence greediness in the shortest time is good idea but it fails.

Part B>

Design of a different greedy algorithm.

i> Sort the trips with respect to the finishing time in ascending order.

ii> and then select the first trip

iii> upon completion of the current trip, choose the first next trip for which  f≤s′.

iv> repeat (ii) until there are no trips left.

Walkthrough with the previous example.

*sorted (ascending order w.r.t. finishing time) = {(4,9) ; ( 11, 12) ; (5,13); (10, 15)}

*choosing the first trip (4,9)

*then we choose the first next trip for which f<=s' ; we choose (11,12) because 9<=12

*then we find no first next trip for which f<=s'. So this is our answer=(4,9) and (11,12)

Part C:

Argument behind the algorithm is the fundamental ideology that since start time is always lesser than finishing time, choosing to complete the minimum finishing time trip results in earlier completion of trips and preparing for the next trip. In contrast to the short time solution here we consider the possibility of completion of larger trips which can be completed before the shorter trips.