Introduction
I personally find greedy problems hard to derive. After struggling with proofs for quite a while, there are a few things I realized. Greedy proofs are very dependent on the rules of the problem. Loosely speaking each optimization problem gives you observations, from those observations, you realize that if you take certain choices while avoiding all others, then it will always be optimal. That realization is termed Greedy.
There are a lot of optimization problems, but only a small subset allows you to break the problem into subproblems where solving them optimally leads to the best global answer. This property, known as Optimal Substructure, is found in both DP and Greedy algorithms. Sadly, not every problem has this, for example, I CANT FIND ANY EXAMPLES. Maybe say we have an array that constantly shuffles around between subsequent queries, and there exists and element $$$\lceil \frac{n}{3} \rceil $$$ times and $$$query(x)$$$ returns number of values $$$x$$$ in the array. And we need to find that element, maybe only good way to do it sample it and probabilistically we will get the answer with in few dozen queries.
While DP and Greedy share the optimal substructure property, DP is essentially "smart brute force", where you define the subproblems and check all transitions to find the best one. In Greedy, however, you have to rigorously prove that ignoring all other choices and taking just one specific path works every single time. This takes the difficulty one notch up from DP.
The idea behind DP is the same everywhere, gather enough observations to define your subproblems, transitions, and base cases. This same idea is explored in a lot of diverse places—there is DP on bitmasks, trees, digits, ranges and On and on.., but there are not many discussions on Greedy. To fill this gap, I would like to discuss a lot of problems and proofs to capture the essence of how to prove Greedy solutions.
Idea
To prove a greedy solution, the arguments are almost always Proof by Contradiction or Induction. The argument goes like this: let's assume a greedy solution $$$G$$$ and a magical optimal solution $$$O$$$ that doesn't follow the greedy choices. Then, given our observations, we prove that either $$$G$$$ performs no worse than $$$O$$$, or that given the constraints, the final solution produced by both strategies will look exactly the same. On the flip side, among many greedy choices, to disprove one, the easiest way is to find a counter-example.
There are a lot of problems i have referenced some of them are, Kanade's Perfect Multiples, Game on Array, Stay or Mirror, Ticket Hoarding, Maximum Running time of N computers, Group Increases, Xor factorization, Divine Tree, etc. Below i have mentioned the Greedy aspects, and some common greedy problems. Sometimes greedy seems obvious and intuitive but try to form a rigorous argument while proving the below mentioned problems.
Problems
Basic problems
Try to come up with formal arguments, to get the hang of it. Basic don't always mean easy.
P1. I have $$$n$$$ items and knapsack of capacity $$$W$$$. The $$$i$$$th item has a value and weight $$$v_i$$$ and $$$w_i$$$, im allowed to take fractions of items. Find the strategy that maximizes the total value.
P2. I running along have infinitely long number line. I can run for $$$M$$$ units without refreshments. There are $$$n$$$ refreshment stalls where $$$i$$$th stall is located at $$$x_i$$$ on the number line for refreshment breaks. Find the strategy that minimizes number of refreshment breaks.
P3. Given 2 integer arrays $$$a$$$ and $$$b$$$ of size $$$n$$$ filled with positive integers. Reorder arrays to maximize $$$\prod_{i=1}^{n} a_{i}^{b_i}$$$. Too easy :P
P4. Given array of $$$n$$$ activities, $$$i$$$th activity takes $$$p_i$$$ time to complete. I want to schedule activities such activities dont overlap,
- Let $$$c_i$$$ be the completion time of the activities. Say $$$i$$$th activity starts at $$$x$$$th time, then its completion time is $$$c_i=x+p_i$$$. Minimize the $$$ \cdot \sum_{i=1}^{n} c_i$$$ , or divide by $$$n$$$ to call it minimum average completion time.
- Given another array $$$s$$$ that tells the starting time of the activities. Find the maximum set of activities you take.
Note: Graph is denoted with $$$H$$$ , as the letter $$$G$$$ represents greedy solution.
By now, we must have gotten some idea about how we try to find properties that connect the greedy solution $$$G$$$ and the optimal solution $$$O$$$ to make them look the same. The same applies to problems involving graphs or trees, where we assume a certain optimal tree $$$T_{O}$$$, or some subgraph $$$H_{O} \subset H$$$, or some partially constructed subtree $$$T_{O}' \subset T_{O} \subset H$$$ basically anything concrete that we can play with and try to form some concrete arguments about their behavior.
P5. Given a undirected graph $$$H=(V,E)$$$ with non-negative weights.
- Find its Minimum spanning tree.
- Find strategy to find the 2nd best Minimum spanning tree.
Ideas used in above
In my opinion, after struggling to not able to make up the correct or satisfying argument its feels very weird to hear when in editorial and in comments people say "Oh thats intuitive.. its obvious.. its trivial" , and i go like "How come?" and they usually replies with, "*Translated Cpp code to English x_x" . Proof by AC is no a real proof ^_^ .
