Greedy algorithm event scheduling

Greedy algorithm interval scheduling problem

An event starts at 9AM and finishes at 6PM. Several volunteers have signed to the event each providing a time period during which they can help. We need to cover the entire time of the event (9AM-6PM) with the least number of volunteers. Assume the next volunteer in line can start helping even before the current one finishes his time. In other words volunteers may have their time overlapped. Describe an algorithm to solve this problem.

Solution

This is an optimization problem that can be solved using a greedy approach. Sort the volunteers in increasing order based on the start time of their period. Sorting can be achieved in O(nlogn) time complexity. Loop through time periods until you find a period that starts at 9AM. If there are more than one that starts at 9AM pick the longest period. Once you pick a period keep looking for the next time period that starts at or before the finish time of the previously selected period. The difference between the finish time of the newly selected time period and the end time of the previously selected time period must be of maximum possible value. If you keep repeating the same steps you will get the least number of volunteers to cover the entire time of the event.

Thanks for reading. Please use the comments section below for feedback.