Given a list of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ...] (si < ei). You need to complete canAttendAllMeetings function and return 1 if a person can attend all given meetings else 0.
There is only one argument in input, list of intervals (Each interval is a list containing two elements where the first element is the start time of that interval and the second element is the end time of that interval).
Return either a 1 or a 0.
We have provided a solution which contains necessary comments to understand the approach used: solution.java
We are asked to determine whether a person can attend all meetings represented by a list of given intervals or not.
In brute force method, we can iterate over each interval and try to find another overlapping interval with the current interval. As this process will take two loops and hence will lead to O(n^2) time complexity.
Hence to optimise, we sort the given array by start time of intervals and if start time are same then we sort by end time of intervals.
As intervals are sorted, we can easily observe a relation between end time of previous interval to start time of current interval to determine overlap. If previous_end time > current start time that means previous and current are overlapping intervals. Hence we will return 0 else else continue to iterate. Here if current means ith interval then previous means i-1th interval.
For better understanding, please have a look at the solution.
O(n log n) where n denotes the number of intervals.
As we are sorting list of n intervals hence it will take O(n log n) time. After sorting we are iterating over n intervals it will take O(n) time. Hence the total time complexity will be O(n log n) + O(n) → O(n log n).
We are not storing anything extra. We are assuming that sorting of n intervals will be in place hence O(1).
O(n) where n denotes the number of intervals.
To read input it will take O(n) as we are reading n intervals, auxiliary space used is O(1) and to store output it will take O(1) hence total space complexity will be O(n).