0% completed
Problem Statement
Given an array of intervals representing ‘N’ appointments, find out if a person can attend all the appointments.
Example 1:
Intervals: [[1,4], [2,5], [7,9]]
Output: false
Explanation: Since [1,4] and [2,5] overlap, a person cannot attend both of these appointments.
Example 2:
Intervals: [[6,7], [2,4], [13, 14], [8,12], [45, 47]]
Output: true
Explanation: None of the appointments overlap, therefore a person can attend all of them.
Example 3:
Intervals: [[4,5], [2,3], [3,6]]
Output: false
Explanation: Since [4,5] and [3,6] overlap, a person cannot attend both of these appointments.
Constraints:
- 1 <= intervals.length <= 10<sup>4</sup>
intervals[i].length == 2- 0 <= start<sub>i</sub> < end<sub>i</sub> <= 10<sup>6</sup>
Solution
To solve this problem, we need to check if any of the given meeting times overlap. The best way to do this is by first sorting the intervals based on their start times. Once sorted, we can then iterate through the list and compare each interval with the previous one to see if there is any overlap.
This approach works efficiently because by sorting the intervals, we ensure that if there is an overlap, it will be between consecutive intervals. This reduces the problem to a simpler check, making the solution both effective and easy to understand.
Step-by-Step Algorithm
- Sort the intervals based on their start times. This ensures that we only need to compare each interval with the previous one.
- Iterate through the sorted list of intervals.
- For each interval from the second one onwards, compare its start time with the end time of the previous interval.
- If the start time of the current interval is less than the end time of the previous interval, return false because it means there is an overlap.
- If no overlaps are found during the iteration, return true indicating that all meetings can be attended without conflicts.
Algorithm Walkthrough
Let's take the example intervals: [[6,7], [2,4], [13, 14], [8,12], [45, 47]]
- Step 1: Sort the intervals based on start times: [[2,4], [6,7], [8,12], [13, 14], [45, 47]].
- Step 2: Iterate through the sorted intervals:
- Compare the second interval ([6, 7]) with the first interval ([2, 4]):
- (6) (start time of second) is not less than (4) (end time of first), so no overlap.
- Compare the third interval ([8, 12]) with the second interval ([6, 7]):
- (8) (start time of third) is not less than (7) (end time of second), so no overlap.
- Compare the fourth interval ([13, 14]) with the third interval ([8, 12]):
- (13) (start time of fourth) is not less than (12) (end time of third), so no overlap.
- Compare the fifth interval ([45, 47]) with the fourth interval ([13, 14]):
- (45) (start time of fifth) is not less than (14) (end time of fourth), so no overlap.
- Compare the second interval ([6, 7]) with the first interval ([2, 4]):
- Step 3: Since no overlaps were found, return true.
Code
Here is what our algorithm will look like:
Time Complexity
The time complexity of the above algorithm is O(N*logN), where ‘N’ is the total number of appointments. Though we are iterating the intervals only once, our algorithm will take O(N * logN) since we need to sort them in the beginning.
Space Complexity
The space complexity of the above algorithm will be O(N), which we need for sorting. For Java, Arrays.sort() uses Timsort, which needs O(N) space.
Similar Problems
Problem 1: Given a list of appointments, find all the conflicting appointments.
Example:
Appointments: [[4,5], [2,3], [3,6], [5,7], [7,8]]
Output:
[4,5] and [3,6] conflict.
[3,6] and [5,7] conflict.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible