N Meetings in One Room

In this article, we will solve the problem of scheduling the maximum number of meetings in one room.

Problem Statement: We are given two arrays, start[] and end[], which denote the start and end times of n meetings respectively. Our task is to determine the maximum number of meetings that can be accommodated in the meeting room without any overlapping.

Example:

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

Output: 4

Input: start[] = {1, 2, 3}, end[] = {4, 4, 4}, n = 3

Output: 1

Solution:

To solve this problem, we will follow these steps:

Steps to Solve:

1.    Pair Start and End Times:

o   Create an array of pairs where each pair consists of a start time and the corresponding end time.

2.    Sort the Meetings:

o   Sort the array of pairs. This way, we always consider the meeting that finishes earliest.

3.    Select Meetings:

o   Initialize a count for the maximum number of meetings.

o   Track the end time of the last selected meeting.

o   Iterate through the sorted meetings and select a meeting if its start time is greater than or equal to the end time of the last selected meeting.

o   Update the end time and increment the count.

Time Complexity: O(N log N)

Space Complexity: O(1)