Given a 2D array arr[][] of the form {start, end} representing the start and end time of N meetings, also given two arrays entrance[] and exist[] representing the opening and closing times of the meeting room respectively, the task is to find the minimum time for which a meeting can be attended. If it is not possible to attend any meeting, then print -1.
Examples:
Input: arr[][] = {{15, 19}, {5, 10}, {7, 25}}, entrance[] = {4, 13, 25, 2}, exist[] = {10, 21}
Output: 6
Explanation:
Meeting 1: Enter at the time 13, attend the meeting in the interval (15, 19) and exit at the time 21. Therefore, total time spent in the meeting = 21 – 13 = 8.
Meeting 2: Enter at the time 4, attend the meeting in (5, 10) and exit at the time 10. Therefore, total time spent in the meeting = 10 – 4 = 6.
Meeting 3: Enter at the time 4, attend the meeting in the interval (7, 25). But after the time 25 there is no closing time. Therefore, total time spent is infinite.
Therefore, minimum units of time that can be spent to attend a meeting is 6.Input: arr[][] = {{1, 2}}, entrance[] = {1, 2}, exist[] = {3, 4}
Output: 2
Naive Approach: The simplest approach to solve this problem is to traverse arr[][] and for each interval {starti, endi}, find the value which just smaller than or equal to arr[i][0] in the array entrance[]. Also, find the value which is just greater than or equal to arr[i][1] in the array exist[]. Finally, print the minimum time to attend exactly one meeting.
Time Complexity: O(N*max(P, M)), where M and P are the size of entrance[]and exist[] arrays.
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is to use Sorting Algorithm and Binary Search technique.
Follow the steps below to solve the problem:
- Sort the arrays entrance[] and exist[] in increasing order.
- Initialize a variable ans to store the minimum time to attend exactly one meeting.
- Traverse the array and for each interval of the meetings, find the value which is just smaller than or equal to starti in the entrance[] array using upper_bound and find the value which is just greater than or equal to endiin the exist[] array using lower_bound.
- Finally, print the minimum time to attend exactly one meeting.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum time to// attend exactly one meetingint minTime(int meeting[][2], int n, vector<int> entrance, int m, vector<int> &exit, int p){ // Stores minimum time to attend // exactly one meeting int ans = INT_MAX; // Sort entrance[] array sort(entrance.begin(), entrance.end()); // Sort exit[] time sort(exit.begin(), exit.end()); // Traverse meeting[][] for (int i = 0; i < n; i++) { // Stores start time of // current meeting int u = meeting[i][0]; // Stores end time of // current meeting int v = meeting[i][1]; // Find just greater value of // u in entrance[] auto it1 = upper_bound(entrance.begin(), entrance.end(), u); // Find just greater or equal value // of u in entrance[] auto it2 = lower_bound(exit.begin(), exit.end(), v); // Stores enter time to attend // the current meeting int start = it1 - entrance.begin() - 1; // Stores exist time after // attending the meeting int end = it2 - exit.begin(); // Update start lies in range [0, m -1] // and end lies in the range [0, p - 1] if (start >= 0 && start < m && end >= 0 && end < p) // Update ans ans = min(ans, exit[end] - entrance[start]); } // Return answer return ans >= INT_MAX ? -1 : ans;}// Driver Codeint main(){ // Stores interval of meeting int meeting[][2] = { { 15, 19 }, { 5, 10 }, { 7, 25 } }; // Stores entrance timings vector<int> entrance = { 4, 13, 25, 2 }; // Stores exit timings vector<int> exit = { 10, 25 }; // Stores total count of meetings int n = (sizeof(meeting)) / sizeof(meeting[0]); // Stores total entrance timings int m = entrance.size(); // Stores total exit timings int p = exit.size(); // Minimum time cout << minTime(meeting, n, entrance, m, exit, p) << endl; return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ static Vector<Integer> exit = new Vector<>(); // Function to find the// minimum time to attend // exactly one meetingstatic int minTime(int meeting[][], int n, int[] entrance, int m, int p){ // Stores minimum time to attend // exactly one meeting int ans = Integer.MAX_VALUE; // Sort entrance[] array Arrays.sort(entrance); // Sort exit[] time Collections.sort(exit); // Traverse meeting[][] for (int i = 0; i < n; i++) { // Stores start time of // current meeting int u = meeting[i][0]; // Stores end time of // current meeting int v = meeting[i][1]; // Find just greater value of // u in entrance[] int it1 = upper_bound(entrance, 0, entrance.length, u); // Find just greater or equal // value of u in entrance[] int it2 = lowerBound(exit, 0, exit.size(), v); // System.out.println(exit.size()); // Stores enter time to attend // the current meeting int start = it1 - 1 ; // Stores exist time after // attending the meeting int end = it2 ; // Update start lies in range [0, m -1] // and end lies in the range [0, p - 1] if (start >= 0 && start < m && end >= 0 && end < p) // Update ans ans = Math.min(ans, exit.get(end) - entrance[start]); } // Return answer return ans >= Integer.MAX_VALUE ? -1 : ans;}static int upper_bound(int[] a, int low, int high, int element){ while(low < high) { int middle = low + (high - low) / 2; if(a[middle] > element) high = middle; else low = middle + 1; } return low;}static int lowerBound(Vector<Integer> vec, int low, int high, int element) { int [] array = new int[vec.size()]; int k = 0; for(Integer val : vec) { array[k] = val; k++; } // vec.clear(); while (low < high) { int middle = low + (high - low) / 2; if (element > array[middle]) { low = middle + 1; } else { high = middle; } } return low;}// Driver Codepublic static void main(String[] args){ // Stores interval of meeting int meeting[][] = {{15, 19}, {5, 10}, {7, 25}}; // Stores entrance timings int []entrance = {4, 13, 25, 2}; // Stores exit timings exit.add(10); exit.add(25); // Stores total count of // meetings int n = meeting.length; // Stores total entrance // timings int m = entrance.length; // Stores total exit // timings int p = exit.size(); // Minimum time System.out.print(minTime(meeting, n, entrance, m, p) + "\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approachfrom bisect import bisect_left, bisect_rightimport sys# Function to find the minimum time to# attend exactly one meetingdef minTime(meeting, n, entrance, m, exit, p): # Stores minimum time to attend # exactly one meeting ans = sys.maxsize # Sort entrance[] array entrance = sorted(entrance) # Sort exit[] time exit = sorted(exit) # Traverse meeting[][] for i in range(n): # Stores start time of # current meeting u = meeting[i][0] # Stores end time of # current meeting v = meeting[i][1] # Find just greater value of # u in entrance[] it1 = bisect_right(entrance, u) # Find just greater or equal value # of u in entrance[] it2 = bisect_left(exit, v) # Stores enter time to attend # the current meeting start = it1 - 1 # Stores exist time after # attending the meeting end = it2 # Update start lies in range [0, m -1] # and end lies in the range [0, p - 1] if (start >= 0 and start < m and end >= 0 and end < p): # Update ans ans = min(ans, exit[end] - entrance[start]) if ans >= sys.maxsize: ans = -1 # Return answer return ans # Driver Codeif __name__ == '__main__': # Stores interval of meeting meeting = [ [ 15, 19 ], [ 5, 10 ], [ 7, 25 ] ] # Stores entrance timings entrance = [ 4, 13, 25, 2 ] # Stores exit timings exit = [ 10, 25 ] # Stores total count of meetings n = len(meeting) # Stores total entrance timings m = len(entrance) # Stores total exit timings p = len(exit) # Minimum time print(minTime(meeting, n, entrance, m, exit, p))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ static List<int> exit = new List<int>(); // Function to find the// minimum time to attend // exactly one meetingstatic int minTime(int [,]meeting, int n, int[] entrance, int m, int p){ // Stores minimum time to attend // exactly one meeting int ans = int.MaxValue; // Sort entrance[] array Array.Sort(entrance); // Sort exit[] time exit.Sort(); // Traverse meeting[,] for(int i = 0; i < n; i++) { // Stores start time of // current meeting int u = meeting[i, 0]; // Stores end time of // current meeting int v = meeting[i, 1]; // Find just greater value of // u in entrance[] int it1 = upper_bound(entrance, 0, entrance.Length, u); // Find just greater or equal // value of u in entrance[] int it2 = lowerBound(exit, 0, exit.Count, v); // Console.WriteLine(exit.Count); // Stores enter time to attend // the current meeting int start = it1 - 1; // Stores exist time after // attending the meeting int end = it2; // Update start lies in range [0, m -1] // and end lies in the range [0, p - 1] if (start >= 0 && start < m && end >= 0 && end < p) // Update ans ans = Math.Min(ans, exit[end] - entrance[start]); } // Return answer return ans >= int.MaxValue ? -1 : ans;}static int upper_bound(int[] a, int low, int high, int element){ while (low < high) { int middle = low + (high - low) / 2; if (a[middle] > element) high = middle; else low = middle + 1; } return low;}static int lowerBound(List<int> vec, int low, int high, int element) { int [] array = new int[vec.Count]; int k = 0; foreach(int val in vec) { array[k] = val; k++; } // vec.Clear(); while (low < high) { int middle = low + (high - low) / 2; if (element > array[middle]) { low = middle + 1; } else { high = middle; } } return low;}// Driver Codepublic static void Main(String[] args){ // Stores interval of meeting int [,]meeting = { { 15, 19 }, { 5, 10 }, { 7, 25 } }; // Stores entrance timings int []entrance = { 4, 13, 25, 2 }; // Stores exit timings exit.Add(10); exit.Add(25); // Stores total count of // meetings int n = meeting.GetLength(0); // Stores total entrance // timings int m = entrance.Length; // Stores total exit // timings int p = exit.Count; // Minimum time Console.Write(minTime(meeting, n, entrance, m, p) + "\n");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to implement// the above approachlet exit = [];// Function to find the// minimum time to attend// exactly one meetingfunction minTime(meeting, n, entrance, m, p){ // Stores minimum time to attend // exactly one meeting let ans = Number.MAX_VALUE; // Sort entrance[] array (entrance).sort(function(a, b){return a - b;}); // Sort exit[] time (exit).sort(function(a, b){return a - b;}); // Traverse meeting[][] for(let i = 0; i < n; i++) { // Stores start time of // current meeting let u = meeting[i][0]; // Stores end time of // current meeting let v = meeting[i][1]; // Find just greater value of // u in entrance[] let it1 = upper_bound(entrance, 0, entrance.length, u); // Find just greater or equal // value of u in entrance[] let it2 = lowerBound(exit, 0, exit.length, v); // System.out.println(exit.size()); // Stores enter time to attend // the current meeting let start = it1 - 1; // Stores exist time after // attending the meeting let end = it2; // Update start lies in range [0, m -1] // and end lies in the range [0, p - 1] if (start >= 0 && start < m && end >= 0 && end < p) // Update ans ans = Math.min(ans, exit[end] - entrance[start]); } // Return answer return ans >= Number.MAX_VALUE ? -1 : ans;}function upper_bound(a, low, high, element){ while(low < high) { let middle = low + Math.floor((high - low) / 2); if (a[middle] > element) high = middle; else low = middle + 1; } return low;}function lowerBound(vec, low, high, element){ let array = new Array(vec.length); let k = 0; for(let val = 0; val < vec.length; val++) { array[k] = vec[val]; k++; } // vec.clear(); while (low < high) { let middle = low + Math.floor((high - low) / 2); if (element > array[middle]) { low = middle + 1; } else { high = middle; } } return low;}// Driver Code // Stores interval of meetinglet meeting = [ [ 15, 19 ], [ 5, 10 ], [ 7, 25 ] ]; // Stores entrance timingslet entrance = [ 4, 13, 25, 2 ];// Stores exit timingsexit.push(10);exit.push(25);// Stores total count of// meetingslet n = meeting.length;// Stores total entrance// timingslet m = entrance.length;// Stores total exit// timingslet p = exit.length;// Minimum timedocument.write(minTime(meeting, n, entrance, m, p) + "<br>");// This code is contributed by unknown2108</script> |
Output:
6
Time Complexity: O(N * max(logP, logM)) where M and P are the lengths of entrance[] and exist[] arrays.
Auxiliary Space: O(1)
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!
