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, a greedy algorithm requires more conditions to be met (the greedy choice property), but it is more efficient.

For example, an algorithm problem that requires exponential time using a brute-force solution can be reduced to polynomial time if overlapping subproblems can be eliminated using dynamic programming. If the greedy choice property is satisfied, the time complexity can be further reduced to linear.

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

For example, if you have 100 banknotes in front of you and can only take ten, how do you get the highest total value? It's clear that choosing the largest denomination remaining each time will lead to the optimal result.

However, most problems do not have the greedy choice property. For instance, in the card game "Dou Di Zhu," if the opponent plays a pair of threes, the greedy strategy would suggest playing the smallest possible card that can beat them. In reality, we might even play a "bomb" card. In such cases, a greedy algorithm is not suitable, and dynamic programming is needed, as discussed in the previous article Dynamic Programming for Game Problems.

1. Problem Overview

To the point, this article addresses a classic greedy algorithm problem, Interval Scheduling, also known as LeetCode Problem 435 Non-Overlapping Intervals:

You are given many closed intervals of the form [start, end]. Design an algorithm to calculate 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.