Week - 4

Greedy algorithm

1. You work as a freelancer and have a pool of 10 projects to work on. For each project, you know how much money you will get for completing the project. You can complete any 3 projects this month. You want to select such projects that you will get the most money by completing them. What are the safe moves in this problem? [ Identify the strategy which helps in obtaining global optimal] (a) If there are more than 3 projects in the pool, remove the project with the lowest payment for completion, don't work on this project. In the other case, remove the first project from the pool and work on this project. Reason:

   Yes, this is a safe move. If there are more than 3 projects in the pool, you won't work on the project with the lowest payment for completion, because you will only work on the 3 projects with the highest payment for completion. If there are at most 3 projects, you will work on all of them. (b) Take the project which you like the most. (c) Take the project for which you can apply the cool new technology that you've recently learned about. (d) Take the project with the highest payment for completion, complete it and remove it from the pool of projects. Reason:

   Yes, this is a safe move. If you take the project with the highest payment for completion and then select two projects with the highest payoff from all the other projects in the pool, you will make the most money.

2. You are going to travel to another city that is located 𝑑 miles away from your home city. Your car can travel at most 𝑚 miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances stop1 stop2 . . . ,stopN from your home city. What is the minimum number of refills needed?

   d = 950
   m = 400
   number of stops = 4
   stops distances = 200 375 550 750
   min refills = 2 [at 375 and at 750]

   Provide a greedy approach for finding the minimum number of refills. If refills are to be minimized, then it should be done at the farthest station reachable from the start (last point where refill is done) d=950 m=400 n=4 stops=[200,375,550,750] i=0 start=0 refills = 0 stops.append(d) while(i<=n): if(stops[i]>(start+400)): start = stops[i-1] refills=refills+1 i=i+1 if(start+m>=d): print(refills) else: print(-1)

3. Minimum number of platforms: Given the arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits. This problem is known as Interval Partitioning (Scheduling all the intervals with minimum number of resources). Use a greedy approach to solve the problem. If there are 3 overlapping intervals at time t then at a minimum three resources are required. Find the number of overlapping intervals at start and departure time of every interval and print the max no of overlapping intervals.