Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Maximum Meetings in One Room

Medium Acceptance 33.57% Points 30

In a company, there is only one meeting room available. The company has N meetings, each with a start time S[i] and a finish time F[i]. The goal is to determine the maximum number of meetings that can be scheduled in the room. A meeting can only be scheduled if its start time is strictly later than the finish time of the previous meeting. If two meetings can be scheduled at the same time, select the one that finishes earlier.

Additionally, print the indices of all the meetings that are selected.

Examples
Example 1

Example 1

Input: N = 4, S = {1, 2, 3, 5}, F = {3, 4, 5, 6}

Output: {1, 4}

Explanation: We can attend the following meetings: The 1st meeting from (1 to 3), Then the 4th meeting from (5 to 6). Thus, we can attend 2 meetings in total.

Example 2

Example 2

Input: N = 3, S = {1, 2, 3}, F = {2, 3, 4}

Output: {1, 3}

Explanation: We can attend the following meetings: The 1st meeting from (1 to 2), Then the 3rd meeting from (3 to 4). Thus, we can attend 2 meetings in total.

Constraints
  • 1 <= N <= 10^5
  • 0 <= S[i] <= F[i] <= 10^9
  • Sum of N over all test cases doesn't exceeds 10^6
Hints
  • Expected Time Complexity: O(N*log(N))
  • Expected Auxiliary Space: O(N)
Topics
Array Sorting Algorithms
Companies
Visa Adobe Flipkart
Added 29 Mar 2025 33.57% acceptance
Ln 1, Col 1Sign in to save your code
4
1 2 3 5
3 4 5 6
1 4