A subset of requests is compatible if no two of them overlap in time, accepting the largest compatible subset possible. Compatible sets of maximum size are optimal.

Rules for selection of requests can vary but not all are desirable: selecting by earliest start time, shortest interval, and least amount of conflicts all have counterexamples. The best choice is selecting based on earliest finish time

A is a compatible set of requests. The goal is to show that the set A is equivalent to the optimal solution, making sure that each element in A finishes at a time less than or equal to the element from the optimal set. Through this process, we conclude the greedy algorithm returns an optimal set A. The algorithm runs in O(n log n) time.

Another problem may ask for all intervals to be satisfied using as few resources as possible. In any instance of Interval Partitioning, the number of resources needed is at least the depth of the sets of intervals. Altering our greedy algorithm to include a depth label allows every interval to be assigned a label. No two overlapping intervals will receive the same label. This schedules every interval on a resource, using a number of resources equal to the depth of the sets of intervals. This is the optimal number of resources needed.

I found the most interesting part of this section was the lecture where we analyzed the algorithms with counterexamples. It gave the most clarity to the problem solving method used here. In addition, I was surprised to see that soling for all intervals was as simple as adding a depth tracker. I expected to implement new rules for obtaining the optimal solution.