PROBLEM SOLVING - GREEDY TRICKS

Greedy Manipulation Approaches

#	Technique	Use Case	Approach	Complexity	Examples
1	Interval scheduling	Max non-overlapping activities	Sort by finish/end; pick compatible next	O(n log n)	Activity selection Meeting rooms Non-overlapping intervals
2	Ratio sorting	Fractional knapsack	Sort value/weight descending; fill greedily	O(n log n)	Fractional knapsack Task assignment
3	Deadline + profit	Job sequencing	Sort profit desc; place in latest free slot	O(n²) or O(n log n)	Job sequencing with deadlines
4	Min-heap merge	Huffman / rope merge	Always combine two smallest costs	O(n log n)	Huffman coding Connect n ropes
5	Event sweep	Platform / resource count	Sort arrivals/departs; sweep counter	O(n log n)	Minimum platforms Meeting rooms II
6	Coin greedy	Change making	Take largest coin ≤ remainder (canonical systems)	O(n)	Indian/US coin systems
7	MST cut property	Minimum spanning tree	Add min edge crossing cut (Prim/Kruskal)	O(E log E)	Prim's Kruskal's
8	Shortest path greedy	Non-negative weights	Dijkstra: pick min distance vertex	O((V+E) log V)	Single-source shortest path
9	Two-pointer greedy	Sorted pairing	Sort both arrays; pair i with i	O(n log n)	Assign mice to holes Min abs diff pairs
10	Monotonic stack	Remove k digits / build min	Pop while top > current and k > 0	O(n)	Remove k digits Daily temperatures
11	Farthest reach	Jump game	Track max index reachable in one pass	O(n)	Jump game I Jump game II variant
12	Tank / deficit	Circular tour	Reset start when tank negative	O(n)	Gas station
13	Post-process greedy	Stock profit	Sum positive adjacent price diffs	O(n)	Buy/sell stock II
14	Max-heap refuel	Fuel stops	Push fuels in range; pop max when stuck	O(n log n)	Minimum refueling stops
15	Frequency heap	String rearrange	Always place most frequent char if legal	O(n log k)	Rearrange string k distance

Related Greedy Algorithm Resources

Simple Programs

Topic-wise Problems