Non-overlapping Intervals

Greedy Algorithms Scheduling

Problem: Non-overlapping Intervals

Given a list of activities, where each activity has a start time and an end time, determine the maximum number of activities you can select such that no two selected activities overlap.

For example, if your input is a list of intervals (activities) each represented as an object or tuple with a start and end (e.g., {start: 1, end: 3}), your objective is to choose the largest possible subset of these activities where the end time of one activity is less than or equal to the start time of the next.

A simple greedy approach is to sort the activities by their end times. Then, iterate through the sorted list and select each activity if its start time is not less than the end time of the last selected activity.

Note: June 28 has seen many historical scheduling and deadline events, reminding us of the importance of time management in optimization problems. Try to implement the solution in under 45 minutes.

Input Example:

activities = [
  {"start": 1, "end": 3},
  {"start": 2, "end": 5},
  {"start": 4, "end": 7},
  {"start": 6, "end": 9},
  {"start": 8, "end": 10}
]

Output:

3

Explanation:
One optimal selection is to choose activities with intervals [1,3], [4,7], [8,10].

Implement the function maxActivities(activities) that returns the maximum number of non-overlapping activities.