Greedy Algorithm for Interval Scheduling Problem

What is a Greedy Algorithm? A greedy algorithm can be considered a special case of dynamic programming. Compared to dynamic programming, using a greedy algorithm requires meeting more conditions (greedy choice property), but it is more efficient.

For example, if a problem requires exponential time with a brute-force approach, using dynamic programming to eliminate overlapping subproblems can reduce it to polynomial time. If it satisfies the greedy choice property, the time complexity can be further reduced to linear.

What is the greedy choice property? Simply put, it means making a locally optimal choice at each step, which leads to a globally optimal result. Note that this is a special property and only a subset of problems possess it.

For instance, if you have 100 RMB notes in front of you and you can only take ten, how do you maximize the total value? Obviously, by always choosing the note with the highest value among the remaining ones, your final selection will be optimal.

However, most problems clearly do not have the greedy choice property. For example, in the card game "Dou Di Zhu," if the opponent plays a pair of threes, the greedy strategy would be to play the smallest card that beats it. But in reality, you might even play a pair of kings. In such cases, a greedy algorithm won't work, and you need to use dynamic programming instead, as discussed in the previous article Dynamic Programming for Game Theory.

I. Problem Overview

Getting back on track, this article solves a classic greedy algorithm problem called Interval Scheduling, which is also LeetCode problem #435 "Non-overlapping Intervals":

You are given many closed intervals of the form [start, end]. Your task is to design an algorithm to determine the maximum number of non-overlapping intervals.

int intervalSchedule(int[][] intvs);

int intervalSchedule(vector<vector<int>>& intvs);

def intervalSchedule(intvs: List[List[int]]) -> int:

func intervalSchedule(intvs [][]int) int

var intervalSchedule = function(intvs) {}

For example, given intvs = [[1,3], [2,4], [3,6]], the maximum number of intervals that do not overlap is 2, specifically [[1,3], [3,6]]. Your algorithm should return 2. Note that intervals with the same boundary are not considered overlapping.

This problem has wide applications in real life. For instance, if you have several events today, each represented by an interval [start, end] indicating the start and end times, how many events can you attend at most? Obviously, you cannot attend two events at the same time, so this problem is essentially about finding the maximum subset of these time intervals that do not overlap.