Greedy Algortihms

Greedy Algorithms

Recent Articles on ‘ Greedy Algorithms ‘ !

• Standard Greedy Algorithms
• Greedy Algorithms in Graphs
• Greedy Algorithms in Operating Systems

• Approximate Greedy Algorithms for NP Complete Problems
• Greedy Algorithms for Special Cases of DP problems
• More Greedy Problems
• Quick Links

Standard Greedy Algorithms :

1. Activity Selection Problem
2. Egyptian Fraction
3. Job Sequencing Problem
4. Huffman Coding
5. Efficient Huffman Coding for sorted input

Greedy Algorithms in Graphs :

1. Kruskal’s Minimum Spanning Tree
2. Prim’s Minimum Spanning Tree
3. Boruvka’s Minimum Spanning Tree
4. Reverse delete algorithm for MST
5. Dijkastra’s Shortest Path Algorithm
6. Dial’s Algorithm
7. Dijkstra’s Algorithm for Adjacency List Representation
8. Prim’s MST for adjacency list representation

Greedy Algorithms in Operating Systems :

1. First Fit algorithm in Memory Management
2. Best Fit algorithm in Memory Management
3. Worst Fit algorithm in Memory Management
4. Shortest Job First Scheduling

Approximate Greedy Algorithms for NP Complete Problems :

1. Traveling Salesman Problem | Set 2 (Approximate using MST)
2. Set cover problem
3. Bin Packing Problem
4. Graph Coloring
5. K-centers problem
6. Shortest superstring problem

Greedy Algorithms for Special Cases of DP problems:

1. Fractional Knapsack Problem
2. Minimum number of coins required

More Greedy Problems:

1. Minimum time to finish all jobs with given constraints
2. Job Sequencing Problem | Set 2 (Using Disjoint Set)
3. Minimum sum of two numbers formed from digits of an array
4. Find Smallest number with given number of digits and digits sum
5. Connect n ropes with minimum cost
6. Minimum number of Platforms required for a railway/bus station
7. Minimum sum of absolute difference of pairs of two arrays
8. Maximize sum of consecutive differences in a circular array
9. Paper cut into minimum number of squares
10. Minimize sum of product of two arrays with permutation allowed
11. Lexicographically smallest array after at-most K consecutive swaps
12. Rearrange characters in a string such that no two adjacent are same
13. Maximum height pyramid from the given array of objects
14. Minimum cost for acquiring all coins with k extra coins allowed with every coin
15. Maximum sum possible equal to sum of three stacks
16. Maximize array sum after k-negations | Set 1
17. Maximize array sum after k-negations | Set 2
18. Rearrange a string so that all same characters become d distance away
19. Minimum Cost to cut a board into squares
20. Minimize cash flow among friends
21. Minimum edges to reverse to make path from a source to a destination
22. Minimize the maximum difference between the heights of towers

Quick Links :

1. Top 20 Greedy Algorithms Interview Questions
2. ‘Practice Problems’ on Greedy Algorithms
3. ‘Quiz’ on Greedy Algorithms
4. Ask a Question on ‘Greedy Algorithms’

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Given a list of input tasks to run, and the cooldown interval, output the minimum number of time slots required to run them.

// Tasks: 1, 1, 2, 1, 2

// Recovery interval (cooldown): 2

// Output: 8 (order is 1 _ _ 1 2 _ 1 2 )

Whats the time and space complexity ? What's the ideal case of space complexity ?

- ttemp3103 December 31, 2017 in United States |

Facebook

https://www.youtube.com/watch?v=R6Skj4bT1HE&feature=youtu.be