-
Notifications
You must be signed in to change notification settings - Fork 8
33. Greedy Algorithm
Video Link
What: A technique to solve problems.
Definition: At present, jo best lage wo le lo.
Example: Markov Process which depends only on the previous state.
- Generally, sorting is done first while applying the greedy technique.
- Sometimes we don't realize that we are using the greedy technique as it comes naturally.
- Practice is "the only key"
This is basic but same time "important".
Problem: For a given denomination (here India's). Find the minimum number of coins required for a certain amount?
Like: 388 we need 8(200+100+50+20+10+5+2+1)
This is a concept more than a question itself.
Note: it is a highly important and frequently used concept but at the same time it is super easy.
⭐ You can solve many questions with this concept only.
Problem: Given n activities with start and finish time. Find maximum activities that can be performed in a given time if only one activity can be performed at a time.
Constraints: 1 <= n <= 1e5, 1 <= start, end <= 1e9(int is enough), start <= end
Quick Note: Create Gantt charts are quite useful for a dry runs.
Pretty Standard Problem, who doesn't know this.
Problem: You have a bad or sack which can hold weight 'w' and you are provided with 'n' objects with profit and weight. Maximize the profit.
Problem: Given n files with their computation time, merge it into one with minimum(cost = computation time, and on merging time adds)
One of the great problems on Spoj to build greedy concepts.
Problem: A group of cows grabbed a truck and ventured on an expedition(a long journey for a specific purpose) deep into the jungle. The truck leaks one unit of fuel every unit of distance it travels.
To repair the truck, the cows need to drive to the nearest town(no more than 1e6 units of distance).On this road, between the town and the current location, there are N(1 <= N <= 1e5) fuels stops where the cows can stop to acquire additional fuel (1...100 units at each stop)
The cows want to make the minimum possible number of stops for fuel on the way to town. The capacity of the tank is sufficiently large to hold any amount of fuel.
The tank can hold any amount of fuel.
Initial Units of fuel: P(1<= P 1e6)
Initial Distance from town: L
Find the minimum number of stops.
Problem: Given Array A[n]. You have to remove n/2 elements exactly from Array A and add it to another array B(initially empty).
Find the min and max values of differences between these two arrays. The difference between these two arrays is defined as the absolute summation of A[i] - B[i]