02 Greedy Techniques - broyda/cp-lib GitHub Wiki
Common techniques
-
Sorting and applying some greey idea
-
Multiset/priority queue - insert/delete based on some property
-
Reversal of approach/thinking backward
-
Splitting dimension - for example, converting a 2 D problem into couple 1D's and arguing for one dimension.
-
Classical ideas - range based etc. (finish first/last etc.)
-
classical problems - machine job allocation
Variants - starting time, length, ending time - Earliest ending time yields the best solution -
Multiset can be used when priority queues are used. Consider multiset as superset of PQs.
-
Knapsack - Dynamic Programming
Fractional knapsack - Greedy
whereas
Activity Selection - Greedy
Weighted Activity Selection - Dynamic Programming