The Maximum Overlap Pattern (Minimum Meeting Rooms with Line Sweep)

The Maximum Overlap Pattern

Some problems give you a list of intervals — pairs of numbers like a start and an end. An interval could be a meeting (start time, end time), a movie showing, or any task that runs over a stretch. A whole family of these problems can be cracked with one simple idea: find the largest number of intervals that are happening at the same moment. That count is called the *maximum overlap*.

If you can rewrite a problem into this template, you can solve it with this pattern:

> Template: Given an array of intervals, find the maximum overlap between them.

The example problem

> Problem: Given the start and end times of some meetings, find the minimum number of meeting rooms needed so that no two meetings clash.

Our meetings are:

• 2, 5
• 5, 9
• 3, 7
• 1, 4

Think about it with everyday logic. A room can hold only one meeting at a time. So how many rooms do we need? Exactly as many as the most meetings that are ever running together. If at the busiest moment 3 meetings overlap, we need 3 rooms — no more, no less. (If nothing ever overlaps, one room is enough.)

So "minimum rooms" is really "maximum overlap" in disguise. That is the clue that this pattern applies.

The line sweep technique

The trick to find the maximum overlap is called line sweep. Imagine a vertical line that slowly moves from left to right across a timeline. Every time it passes a start, one more meeting becomes active. Every time it passes an end, one meeting finishes. We just watch how many are active and remember the highest count we ever saw.

Step 1 — Break intervals into points

Instead of keeping each interval as a pair, split it into two separate events: a start point and an end point. So 2, 5 becomes a 2 start and a 5 end. After doing this for all four meetings we get a flat list of 8 points.

Step 2 — Sort all the points

Sort the points by their time value. After sorting we get:

1 start, 2 start, 3 start, 4 end, 5 end, 5 start, 7 end, 9 end

One subtle but important detail: when a start and an end happen at the *same* time, put the end first. A meeting that ends at 5 has freed its room, so a meeting starting at 5 can reuse it. In code this is arranged neatly by labelling ends with 'e' and starts with 's', because the character 'e' sorts before 's'. That is why in the sorted list above 5 end comes before 5 start.

Step 3 — Sweep and count

Use two counters:

• rooms — how many meetings are active right now.
• minRooms — the largest value rooms has ever reached (this is our final answer).

Both start at 0. Now walk through the sorted points left to right:

• Hit a start point → a new meeting begins → rooms = rooms + 1. Then check: if rooms > minRooms, update minRooms.
• Hit an end point → a meeting finished → rooms = rooms - 1.

Let us run it on our sorted list and watch the two counters:

| Point | Action | rooms | minRooms |

|-------|--------|---------|------------|

| 1 start | +1 | 1 | 1 |

| 2 start | +1 | 2 | 2 |

| 3 start | +1 | 3 | 3 |

| 4 end | −1 | 2 | 3 |

| 5 end | −1 | 1 | 3 |

| 5 start | +1 | 2 | 3 |

| 7 end | −1 | 1 | 3 |

| 9 end | −1 | 0 | 3 |

The peak was 3 — three meetings (1,4, 2,5, 3,7) were all running between times 3 and 4. So the answer is 3 meeting rooms.

The code

class Solution {
public:
    int minimumMeetingRooms(vector<vector<int>> &meetings) {
        // Create a dynamic array to store start and end times
        vector<pair<int, char>> times;
        for (auto &interval : meetings) {
            // Add start and end times to the times array
            times.push_back(make_pair(interval[0], 's'));
            times.push_back(make_pair(interval[1], 'e'));
        }
        // Sort the times array, end times come before
        // start times as 'e' < 's'
        sort(times.begin(), times.end());
        // Initialize 'rooms' and 'minRooms' to 0
        int rooms = 0, minRooms = 0;
        // ... sweep: +1 on 's', -1 on 'e', track minRooms ...
    }
};

The whole thing finishes in a single pass over the sorted list, so it is fast and simple.

When to reach for this pattern

Whenever a problem hands you intervals and asks "how many overlap", "how many rooms/resources", "what is the busiest moment", or something that reduces to those, think maximum overlap + line sweep. A few classic problems that use it:

• Minimum meeting rooms
• Remove intervals
• Busiest interval
• Peak resource requirement