N meetings in one room

You are given timings of n meetings in the form of (start[i], end[i]) where start[i] is the start time of meeting i and end[i] is the finish time of meeting i. Return the maximum number of meetings that can be accommodated in a single meeting room, when only one meeting can be held in the meeting room at a particular time. 

Note: The start time of one chosen meeting can’t be equal to the end time of the other chosen meeting.

Examples :

Input: n = 6, start[] = [1, 3, 0, 5, 8, 5], end[] =  [2, 4, 6, 7, 9, 9]
Output: 4
Explanation: Maximum four meetings can be held with given start and end timings. The meetings are - (1, 2), (3, 4), (5,7) and (8,9)

Input: n = 3, start[] = [10, 12, 20], end[] = [20, 25, 30]
Output: 1
Explanation: Only one meetings can be held with given start and end timings.

Expected Time Complexity: O(n*logn)
Expected Auxilliary Space: O(n)

Constraints:
1 ≤ n ≤ 10⁵
0 ≤ start[i] < end[i] ≤ 10⁶

Approach 01:

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    // Function to find the maximum number of meetings that can be performed in a meeting room.
    int maxMeetings(int n, int start[], int end[]) {
        vector<pair<int, int>> meetings(n);

        // Store start and end times in the meetings vector
        for (int i = 0; i < n; i++) {
            meetings[i] = {start[i], end[i]};
        }

        // Sort meetings by their end times
        sort(meetings.begin(), meetings.end(), [](pair<int, int>& m1, pair<int, int>& m2) {
            return m1.second < m2.second;
        });

        int maxMeetings = 1; // Initialize the maximum number of meetings
        int lastEndTime = meetings[0].second; // Track the end time of the last selected meeting

        // Iterate through the meetings to select the maximum number of non-overlapping meetings
        for (int i = 1; i < n; i++) {
            if (meetings[i].first > lastEndTime) {
                maxMeetings++;
                lastEndTime = meetings[i].second;
            }
        }

        return maxMeetings;
    }
};

from typing import List

class Solution:
    # Function to find the maximum number of meetings that can be performed in a meeting room.
    def maximumMeetings(self, n: int, start: List[int], end: List[int]) -> int:
        # Combine start and end times into a list of tuples
        meetings = [(start[i], end[i]) for i in range(n)]

        # Sort meetings by their end times
        meetings.sort(key=lambda m: m[1])

        maxMeetings = 1  # Initialize the maximum number of meetings
        lastEndTime = meetings[0][1]  # Track the end time of the last selected meeting

        # Iterate through the meetings to select the maximum number of non-overlapping meetings
        for i in range(1, n):
            if meetings[i][0] > lastEndTime:
                maxMeetings += 1
                lastEndTime = meetings[i][1]

        return maxMeetings

Time Complexity

• Sorting Meetings:

  Sorting the meetings based on their end times takes \( O(n \log n) \) time, where \( n \) is the number of meetings.

• Iterating Through Meetings:

  Iterating through the sorted list of meetings to count the maximum number of non-overlapping meetings takes \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting step, so it is \( O(n \log n) \).

Space Complexity

• Auxiliary Space:

  We use a vector of pair to store the start and end times of the meetings, which takes \( O(n) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) due to the space required for storing the meetings.