Lemma (4.1)
A is a compatible set of requests.
Proof:
- The first one chosen does not have any conflicts.
- Then we remove all requests conflicting with the chosen one every time we choose a new one.
- So no conflicts by construction.
Imagine you're trying to schedule meetings in a conference room. The greedy algorithm picks a meeting, then throws out any other meeting that overlaps with it. It repeats this process, ensuring that no two meetings ever overlap.