A greedy algorithm optimizes some criterion by taking the most optimization on a step by step basis without direct regard to future iterations. For a given problem, there can be many possible greedy algorithms. The challenge is finding greedy algorithms which are effective and proving their quality.

Interval scheduling involves an effort to schedule the highest possible number of activities in a set amount of time without allowing them to overlap. Some activities are longer than others. We attempt to conceive a greedy algorithm to maximize the number of compatible activities which can be scheduled in any given situation. Simply choosing the activities which start the soonest for our available time does not work as this approach does not account for differing duration. Further, we cannot simply select the activities in the order of their individual running times. One reason for this is because one short activity may overlap with multiple other activities,making it better to choose them instead. For our optimal greedy stays ahead solution,we select the activities with the least number of conflicts with other activities in the order which they start. This approach greedily attempts to minimize the number of conflicts for each step. We can prove that this is the optimal solution by showing that it returns an optimal set A. This involves a simple contradiction. In short, if A is not optimal then it must contain at-least one fewer activities than produced by another solution. The missing activity could not have overlapped the other activities in A given the nature of the algorithm. Thus, the fact that it is not contained within A is a contradiction. This algorithm runs in O(n log(n)) time. The longest part is creating the sorted list of activities at the beginning(all other parts take at most O(n) time). The above scenario may be oversimplified in two key ways: we assume that we know (or the algorithm knows) the set of activities and it is possible that each activity has a different value of priority. This is an example of interval scheduling. Another related problem is interval partitioning. This also involves activities spanning different lengths of time. However, now we must include all activities and separate subsets of activities into different “rooms” such that none overlap. The goal is to achieve this using the smallest number of rooms possible, something which can be achieved with a greedy algorithm.