Introduction

Fitting as many events into a schedule as possible is a classic computational problem that often arises in various fields such as operations research, resource planning, and computer science. The problem is typically known as the "Activity Selection Problem" or the "Interval Scheduling Maximization Problem." The goal is to select a maximum number of non-overlapping intervals (events) from a given list of intervals.

Problem Definition

Given a set of events, each with a start and end time, the objective is to find the maximum number of events that can be scheduled without overlapping.

Example

Consider the following set of events:

• Event A: `(1, 3)`
• Event B: `(2, 5)`
• Event C: `(4, 6)`
• Event D: `(6, 8)`
• Event E: `(5, 9)`

The task is to schedule as many non-overlapping events as possible.

Greedy Algorithm Approach

A popular method to solve this problem is using a Greedy algorithm. The approach involves the following steps:

1. Sort Events: Sort all events by their end times in non-decreasing order.
2. Select First Event: Select the first event in the sorted list and add it to the schedule.
3. Iterate and Compare: Check subsequent events and add an event to the schedule only if its start time is greater than or equal to the end time of the last selected event.

Pseudocode for Greedy Algorithm

• Ordered Events: A (1, 3), B (2, 5), C (4, 6), D (6, 8), E (5, 9)
• Add Event A `(1, 3)`
• Event B overlaps with A. Skip.
• Event C start time `(4)` is after A end time `(3)`. Add C.
• Event D start time `(6)` is after C end time `(6)`. Add D.
• Event E overlaps with C and D. Skip.