Meeting Room
Merging Overlapping Intervals: Meeting Room
The task of merging overlapping intervals is a frequent problem in computer science, often encountered in scheduling and timeline management scenarios.
In this article, we’ll explore how to merge intervals and return a concise, non-overlapping set that covers all the given ranges.
Problem Description
You are given an array of intervals where each interval is represented as intervals[i] = [start_i, end_i]. Your task is to merge all overlapping intervals into a single interval whenever possible and return the resulting array.
Key Points:
Overlapping Definition: Two intervals overlap if their ranges have at least one common point.
- For example:
[1,2]and[3,4]are non-overlapping.[1,2]and[2,3]overlap, as they share the point2.
- For example:
Goal: Minimize the total number of intervals by merging overlapping ones.
Example 1
Input: intervals = [(0,30),(5,10),(15,20)]
Output: false
Explanation:
(0,30)and(5,10)will conflict(0,30)and(15,20)will conflict
Example 2
Input: intervals = [(5,8),(9,15)]
Output: true
Explanation:
- (0,8),(8,10) is not considered a conflict at 8
Approach to Solve the Problem
To solve this problem effectively, we can use the following approach:
Step 1: Sort the Intervals
- Sorting the intervals by their start time ensures that overlapping intervals appear consecutively in the list. This makes it easier to merge them.
Step 2: Merge Overlapping Intervals
- Use a result list to store merged intervals.
- Compare each interval with the last interval in the result list:
- If they overlap, merge them by updating the end of the last interval to the maximum end time.
- If they don’t overlap, add the current interval to the result list.
Algorithm
- Sort the intervals based on their start time.
- Initialize an empty list
mergedto store the result. - Iterate through the sorted intervals:
- If the current interval overlaps with the last merged interval, merge them.
- Otherwise, add the current interval to the result list.
There are mainly three approach to solve this problem –
- Brute Force
- Sweep Line Algorithm
- Greedy
1. Brute Force
- Time complexity: O(2^n)
- Space complexity: O(1)
Python
C++
Java
JavaScript
Python
"""
Definition of Interval:
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
def canAttendMeetings(self, intervals: List[Interval]) -> bool:
n = len(intervals)
for i in range(n):
A = intervals[i]
for j in range(i + 1, n):
B = intervals[j]
if min(A.end, B.end) > max(A.start, B.start):
return False
return True
C++
/**
* Definition of Interval:
* class Interval {
* public:
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
* }
*/
class Solution {
public:
bool canAttendMeetings(vector& intervals) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
Interval& A =intervals[i];
for (int j = i + 1; j < n; j++) {
Interval& B =intervals[j];
if (min(A.end, B.end) > max(A.start, B.start)) {
return false;
}
}
}
return true;
}
};
Java
/**
* Definition of Interval:
* public class Interval {
* public int start, end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
public boolean canAttendMeetings(List intervals) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
Interval A = intervals.get(i);
for (int j = i + 1; j < n; j++) {
Interval B = intervals.get(j);
if (Math.min(A.end, B.end) > Math.max(A.start, B.start)) {
return false;
}
}
}
return true;
}
}
JavaScript
/**
* Definition of Interval:
* class Interval {
* constructor(start, end) {
* this.start = start;
* this.end = end;
* }
* }
*/
class Solution {
/**
* @param {Interval[]} intervals
* @returns {boolean}
*/
canAttendMeetings(intervals) {
const n = intervals.length;
for (let i = 0; i < n; i++) {
const A = intervals[i];
for (let j = i + 1; j < n; j++) {
const B = intervals[j];
if (Math.min(A.end, B.end) > Math.max(A.start, B.start)) {
return false;
}
}
}
return true;
}
}
2. Sorting
Time & Space Complexity
- Time complexity: O(nlogn)
- Space complexity: O(1) or O(n) depending on the sorting algorithm.
Code
C++
Java
Python
JavaScript
C++
/**
* Definition of Interval:
* class Interval {
* public:
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
* }
*/
class Solution {
public:
bool canAttendMeetings(vector& intervals) {
sort(intervals.begin(), intervals.end(), [](auto& x, auto& y) {
return x.start < y.start;
});
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i].start < intervals[i - 1].end) {
return false;
}
}
return true;
}
};
Java
/**
* Definition of Interval:
* public class Interval {
* public int start, end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
public boolean canAttendMeetings(List intervals) {
Collections.sort(intervals, Comparator.comparingInt(i -> i.start));
for (int i = 1; i < intervals.size(); i++) {
Interval i1 = intervals.get(i - 1);
Interval i2 = intervals.get(i);
if (i1.end > i2.start) {
return false;
}
}
return true;
}
}
Python
"""
Definition of Interval:
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
def canAttendMeetings(self, intervals: List[Interval]) -> bool:
intervals.sort(key=lambda i: i.start)
for i in range(1, len(intervals)):
i1 = intervals[i - 1]
i2 = intervals[i]
if i1.end > i2.start:
return False
return TrueJavaScript
/**
* Definition of Interval:
* class Interval {
* constructor(start, end) {
* this.start = start;
* this.end = end;
* }
* }
*/
class Solution {
/**
* @param {Interval[]} intervals
* @returns {boolean}
*/
canAttendMeetings(intervals) {
intervals.sort((a, b) => a.start - b.start);
for (let i = 1; i < intervals.length; i++) {
if (intervals[i].start < intervals[i - 1].end) {
return false;
}
}
return true;
}
}
