Given a set of intervals (tasks/meetings) with start and end times, how do you pick the maximum number of non-overlapping intervals?

Think of a Movie Marathon:

1. You have a list of movies you want to see.
2. Some movies overlap in time.
3. To see the most movies possible, which one should you choose first?
4. The Greedy Secret: Always pick the movie that Finishes Earliest.
5. Why? Because the earlier a movie finishes, the more time you have left in the day to see other movies!

---

The Algorithm

1. Sort all intervals by their End Time.
2. Pick the first interval.
3. For the remaining intervals, if the start time is $\ge$ the end time of the last picked interval, pick it.
4. Repeat.

Why not sort by Start Time?

If you pick a movie that starts at 8:00 AM but lasts for 10 hours, you've blocked your whole day. Sorting by end time ensures you keep as much "future" available as possible.

---

javascript Standard
/**
 * Max meetings - O(n log n)
 */
function maxMeetings(intervals) {
  // 1. Sort by end time
  intervals.sort((a, b) => a.end - b.end);

  let count = 0;
  let lastEndTime = -1;

  for (let interval of intervals) {
    if (interval.start > lastEndTime) {
      count++;
      lastEndTime = interval.end;
    }
  }

  return count;
}

// Example
const meetings = [
  {start: 1, end: 2},
  {start: 3, end: 4},
  {start: 0, end: 6},
  {start: 5, end: 7},
  {start: 8, end: 9},
  {start: 5, end: 9}
];
console.log(maxMeetings(meetings)); // Output: 4

---

Variations

• Minimum Meeting Rooms: How many rooms do you need to hold ALL meetings? (Use a Min-Heap on end times).
• Activity Selection: The same logic as interval scheduling.
• Insert Interval: Adding a new meeting to an already sorted list.

Tip

Whenever you see "Intervals" or "Scheduling", your first thought should always be Sort by End Time. ⏱️