Given a two-dimensional array arr[][] of dimensions N * 2 which contains the starting and ending time for N meetings on a given day. The task is to print a list of time slots during which the most number of concurrent meetings can be held.
Examples:
Input: arr[][] = {{100, 300}, {145, 215}, {200, 230}, {215, 300}, {215, 400}, {500, 600}, {600, 700}}
Output: [215, 230]
Explanation:
The given 5 meetings overlap at {215, 230}.Input: arr[][] = {{100, 200}, {50, 300}, {300, 400}}
Output: [100, 200]
Approach: The idea is to use a Min-Heap to solve this problem. Below are the steps:
- Sort the array based on the start time of meetings.
- Initialize a min-heap.
- Initialize variables max_len, max_start and max_end to store maximum size of min heap, start time and end time of concurrent meetings respectively.
- Iterate over the sorted array and keep popping from min_heap until arr[i][0] becomes smaller than the elements of the min_heap, i.e. pop all the meetings having ending time smaller than the starting time of current meeting, and push arr[i][1] in to min_heap.
- If the size of min_heap exceeds max_len, then update max_len = size(min_heap), max_start = meetings[i][0] and max_end = min_heap_element.
- Return the value of max_start and max_end at the end.
Below is the implementation of the above approach:
C++14
// C++14 implementation of the// above approach#include <bits/stdc++.h>using namespace std;bool cmp(vector<int> a,vector<int> b){ if(a[0] != b[0]) return a[0] < b[0]; return a[1] - b[1];}// Function to find time slot of// maximum concurrent meetingvoid maxConcurrentMeetingSlot( vector<vector<int>> meetings){ // Sort array by // start time of meeting sort(meetings.begin(), meetings.end(), cmp); // Declare Minheap priority_queue<int, vector<int>, greater<int>> pq; // Insert first meeting end time pq.push(meetings[0][1]); // Initialize max_len, // max_start and max_end int max_len = 0, max_start = 0; int max_end = 0; // Traverse over sorted array // to find required slot for(auto k : meetings) { // Pop all meetings that end // before current meeting while (pq.size() > 0 && k[0] >= pq.top()) pq.pop(); // Push current meeting end time pq.push(k[1]); // Update max_len, max_start // and max_end if size of // queue is greater than max_len if (pq.size() > max_len) { max_len = pq.size(); max_start = k[0]; max_end = pq.top(); } } // Print slot of maximum // concurrent meeting cout << max_start << " " << max_end;}// Driver Codeint main(){ // Given array of meetings vector<vector<int>> meetings = { { 100, 200 }, { 50, 300 }, { 300, 400 } }; // Function call maxConcurrentMeetingSlot(meetings);}// This code is contributed by mohit kumar 29 |
Java
// Java implementation of the// above approachimport java.util.*;import java.lang.*;class GFG { // Function to find time slot of // maximum concurrent meeting static void maxConcurrentMeetingSlot( int[][] meetings) { // Sort array by // start time of meeting Arrays.sort(meetings, (a, b) -> (a[0] != b[0]) ? a[0] - b[0] : a[1] - b[1]); // Declare Minheap PriorityQueue<Integer> pq = new PriorityQueue<>(); // Insert first meeting end time pq.add(meetings[0][1]); // Initialize max_len, // max_start and max_end int max_len = 0, max_start = 0; int max_end = 0; // Traverse over sorted array // to find required slot for (int[] k : meetings) { // Pop all meetings that end // before current meeting while (!pq.isEmpty() && k[0] >= pq.peek()) pq.poll(); // Push current meeting end time pq.add(k[1]); // Update max_len, max_start // and max_end if size of // queue is greater than max_len if (pq.size() > max_len) { max_len = pq.size(); max_start = k[0]; max_end = pq.peek(); } } // Print slot of maximum // concurrent meeting System.out.println( max_start + " " + max_end); } // Driver Code public static void main(String[] args) { // Given array of meetings int meetings[][] = { { 100, 200 }, { 50, 300 }, { 300, 400 } }; // Function Call maxConcurrentMeetingSlot(meetings); }} |
Python3
import heapqdef cmp(a, b): if a[0] != b[0]: return a[0] < b[0] return a[1] - b[1]def maxConcurrentMeetingSlot(meetings): meetings.sort(key=lambda x: (x[0], x[1])) pq = [] # Minheap # Insert first meeting end time heapq.heappush(pq, meetings[0][1]) # Initialize max_len, max_start, and max_end max_len = 0 max_start = 0 max_end = 0 # Traverse over sorted array to find the required slot for k in meetings: # Pop all meetings that end before the current meeting while pq and k[0] >= pq[0]: heapq.heappop(pq) # Push the current meeting end time heapq.heappush(pq, k[1]) # Update max_len, max_start, and max_end if the size of the queue is greater than max_len if len(pq) > max_len: max_len = len(pq) max_start = k[0] max_end = pq[0] # Print the slot of the maximum concurrent meeting print(max_start, max_end)# Driver Codeif __name__ == "__main__": # Given array of meetings meetings = [[100, 200], [50, 300], [300, 400]] # Function call maxConcurrentMeetingSlot(meetings) |
C#
using System;using System.Collections.Generic;class Program{ // Custom comparator for sorting meetings static int CompareMeetings(List<int> a, List<int> b) { if (a[0] != b[0]) return a[0].CompareTo(b[0]); return a[1].CompareTo(b[1]); } // Function to find the time slot of maximum concurrent meetings static void MaxConcurrentMeetingSlot(List<List<int>> meetings) { // Sort the array by the start time of meetings meetings.Sort(CompareMeetings); // Declare MinHeap SortedSet<int> minHeap = new SortedSet<int>(); // Insert the end time of the first meeting minHeap.Add(meetings[0][1]); // Initialize max_len, max_start, and max_end int maxLen = 0, maxStart = 0, maxEnd = 0; // Traverse over the sorted array to find the required slot foreach (var meeting in meetings) { // Remove all meetings that end before the current meeting while (minHeap.Count > 0 && meeting[0] >= minHeap.Min) minHeap.Remove(minHeap.Min); // Add the end time of the current meeting minHeap.Add(meeting[1]); // Update maxLen, maxStart, and maxEnd if the size of the // heap is greater than maxLen if (minHeap.Count > maxLen) { maxLen = minHeap.Count; maxStart = meeting[0]; maxEnd = minHeap.Min; } } // Print the time slot of maximum concurrent meeting Console.WriteLine(maxStart + " " + maxEnd); }// Driver code static void Main() { // Given list of meetings List<List<int>> meetings = new List<List<int>>() { new List<int> { 100, 200 }, new List<int> { 50, 300 }, new List<int> { 300, 400 } }; // Function call MaxConcurrentMeetingSlot(meetings); }} |
Output
100 200
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!