Greedy Algorithm for Interval Scheduling Problem

What is a greedy algorithm? A greedy algorithm is a special case of dynamic programming. Compared to dynamic programming, greedy algorithms need to meet more conditions (the "greedy choice property"). But if you can use a greedy algorithm, it is usually faster than dynamic programming.

For example, if a problem needs exponential time with brute-force, using dynamic programming can reduce the time to polynomial by removing repeated subproblems. If the problem also meets the greedy choice property, you can make it even faster, reaching linear time.

What is the greedy choice property? In simple words: at each step, you make the best local choice, and this leads to the best overall result. But remember, only some problems have this special property.

For example, you have 100 bills and you can only pick 10. You want the largest total value. The best way is to always pick the highest value bill left. In this case, the greedy choice gives you the best result.

However, most problems do not have the greedy choice property. For example, in certain card games, you might not always play the smallest card that beats the opponent, sometimes you might need to use your biggest card for a better strategy. In these cases, greedy does not work and you need dynamic programming. You can read more in Dynamic Programming for Game Problems.

1. Problem Overview

Back to the main topic. This article will solve a classic greedy algorithm problem: Interval Scheduling, which is LeetCode problem 435 "Non-overlapping Intervals".

You are given many closed intervals like [start, end]. Please design an algorithm to find 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, intvs = [[1,3], [2,4], [3,6]]. The answer is 2, because you can choose [[1,3], [3,6]] without overlap. Your algorithm should return 2. Note: intervals that just touch at the boundary are not considered overlapping.

This problem has many real-life uses. For example, you have several events today, each with a start and end time [start, end]. What is the maximum number of events you can attend? Obviously, you cannot attend two events at the same time. So, this problem is about finding the largest subset of non-overlapping time intervals.

2. Greedy Solution

3. Application Examples