N meetings in one room | Greedy Solution

The N Meetings in One Room problem is a classic example of the Greedy Algorithm. It focuses on scheduling tasks in such a way that the maximum number of non-overlapping activities can take place. This problem is very common in coding interviews and is closely related to the Activity Selection Problem.

In this blog, we will understand the problem, explore the greedy approach that guarantees the optimal result, and go through the Python implementation step by step.

Here’s the [Problem Link] to begin with.

Problem Statement – What Does the Problem Say?

You are given two arrays:

• start[] – the starting times of meetings
• end[] – the ending times of meetings

Your task is to find the maximum number of meetings that can be scheduled in a single room such that no two meetings overlap.

Example 1:

Input: 
start = [1, 3, 0, 5, 8, 5] 
end   = [2, 4, 6, 7, 9, 9]

Output: 4
Explanation:
One of the possible selections is meetings at:
(1,2), (3,4), (5,7), (8,9)
So, maximum 4 meetings can be held in the room.

Example 2:

Input:
start = [10, 12, 20]
end   = [20, 25, 30]

Output: 2
Explanation:
We can schedule meetings (10,20) and (20,30).

The problem essentially asks: How can we schedule the maximum number of non-overlapping meetings in one room?

Intuition and Approach (Optimal – Greedy)

The greedy approach works perfectly here because the best strategy is always to select the meeting that finishes earliest.

Why does this work?

• If a meeting ends early, the room becomes available sooner, allowing more meetings to fit in.
• By always picking the meeting with the smallest finishing time that does not overlap with previously chosen meetings, we maximize the number of scheduled meetings.

Steps to Solve:

1. Pair each meeting with its start and end time.
2. Sort all meetings based on their end time (if two meetings have the same end time, sort by start time).
3. Select the first meeting and keep track of its end time.
4. For every other meeting:
   • If its start time is greater than the end time of the last selected meeting, select it.
   • Update the end time to the current meeting’s end time.
5. Continue until all meetings are checked.

This greedy strategy ensures that we always make the most optimal choice at each step.

Code Implementation

Here’s the Python code for the N Meetings in One Room problem using the greedy method (with added comments for clarity):

class Meeting:
    def __init__(self, start, end, position):
        self.start = start
        self.end = end
        self.position = position


class Solution:
    def maximumMeetings(self, start, end):
        n = len(start)
        # Create Meeting objects with start, end, and position
        meets = [Meeting(start[i], end[i], i + 1) for i in range(n)]
        
        # Sort meetings by end time (then by start time if needed)
        meets.sort(key=lambda x: (x.end, x.start))
        
        lastTime = meets[0].end
        count = 1  # Select the first meeting by default
        
        # Iterate through the rest of the meetings
        for i in range(1, n):
            if meets[i].start > lastTime:
                count += 1
                lastTime = meets[i].end
                
        return count

Code Explanation

• First, each meeting is represented by a Meeting object storing its start time, end time, and position.
• The list of meetings is sorted by end times. This ensures that the earliest finishing meeting is always considered first.
• The algorithm starts by picking the first meeting.
• For each subsequent meeting, we check if its start time is greater than the end time of the last chosen meeting.
  • If yes, we select it and update the last end time.
  • If no, we skip it to avoid overlap.
• The variable count keeps track of how many meetings can be scheduled.

For example, if start = [1,3,0,5,8,5] and end = [2,4,6,7,9,9]:

• Sorted by end times → [(1,2), (3,4), (0,6), (5,7), (8,9), (5,9)]
• Select (1,2) → last end = 2
• Next, (3,4) → start 3 > 2, so select → last end = 4
• Next, (0,6) → start 0 ≤ 4, skip
• Next, (5,7) → start 5 > 4, so select → last end = 7
• Next, (8,9) → start 8 > 7, so select → last end = 9
• Total meetings = 4

Time and Space Complexity

• Time Complexity:
  • Creating Meeting objects: O(n)
  • Sorting meetings: O(n log n)
  • Iterating through meetings: O(n)
  • Overall: O(n log n)
• Space Complexity:
  • Extra space for storing meetings list: O(n)

This makes the approach efficient and suitable for large inputs.

Conclusion

The N Meetings in One Room problem is a direct application of the Greedy Algorithm. By always choosing the meeting that finishes earliest, we maximize the total number of non-overlapping meetings that can be scheduled.

The approach runs in O(n log n) time due to sorting and uses O(n) space, making it both efficient and optimal.

This problem is an excellent example of how greedy strategies can be applied effectively in scheduling and resource allocation problems.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.