Insert an interval by merging overlapping intervals
Insert the specified interval into a collection of non-overlapping intervals that has been organized by the start time of each interval. If the new interval causes intervals to overlap, merge the overlapped intervals.
For example,
Input:
intervals = [(1, 5), (7, 8), (9, 10), (12, 15)]
interval = (5, 9)
Output: [(1, 10), (12, 15)]
Explanation: The interval (5, 9) overlaps with (1, 5), (7, 8), (9, 10)
Input:
intervals = [(2, 5), (7, 9)]
interval = (3, 4)
Output: [(2, 5), (7, 9)]
Explanation: The interval (3, 4) overlaps with (2, 5)
intervals = [(1, 5), (7, 8), (9, 10), (12, 15)]
interval = (5, 9)
Output: [(1, 10), (12, 15)]
Explanation: The interval (5, 9) overlaps with (1, 5), (7, 8), (9, 10)
Input:
intervals = [(2, 5), (7, 9)]
interval = (3, 4)
Output: [(2, 5), (7, 9)]
Explanation: The interval (3, 4) overlaps with (2, 5)
The idea is very simple: add an interval to the result if it does not overlap the given interval; otherwise, combine all overlapped intervals into one and push the resulting interval to the result. The implementation can be seen below in C++, Java, and Python.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <vector> using namespace std; // Data structure to store an interval struct Interval { int begin, end; bool operator<(Interval const &i) { return (end < i.end); } }; vector<Interval> mergeIntervals(vector<Interval> &intervals, Interval const &interval) { vector<Interval> result; // base case if (intervals.empty()) { result.push_back(interval); return result; } int i = 0; while (i < intervals.size()) { // if the current interval doesn't overlap with the specified interval if (intervals[i].end < interval.begin || intervals[i].begin > interval.end) { // push current interval to the result result.push_back(intervals[i++]); } else { // if the current interval overlaps with the specified interval, // merge all overlapping intervals into one int start = interval.begin, end = interval.end; while (i < intervals.size() && intervals[i].begin <= interval.end) { start = min(start, intervals[i].begin); end = max(end, intervals[i].end); i++; } // push the merged interval to the result result.push_back({start, end}); } } return result; } int main() { vector<Interval> intervals = { { 1, 5 }, { 7, 8 }, { 9, 10 }, { 12, 15 } }; Interval interval = {5, 9}; vector<Interval> result = mergeIntervals(intervals, interval); for (Interval &interval: result) { cout << '{' << interval.begin << ", " << interval.end << "}\n"; } return 0; } |
Output:
{1, 10}
{12, 15}
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
import java.util.ArrayList; import java.util.List; // A class to store an interval class Interval { int begin, end; Interval(int begin, int end) { this.begin = begin; this.end = end; } @Override public String toString() { return "{" + begin + ", " + end + "}"; } } class Main { public static List<Interval> mergeIntervals(List<Interval> intervals, Interval interval) { List<Interval> result = new ArrayList<>(); // base case if (intervals.isEmpty()) { result.add(interval); return result; } int i = 0; while (i < intervals.size()) { // if the current interval doesn't overlap with the specified interval if (intervals.get(i).end < interval.begin || intervals.get(i).begin > interval.end) { // push current interval to the result result.add(intervals.get(i++)); } else { // if the current interval overlaps with the specified interval, // merge all overlapping intervals into one int start = interval.begin, end = interval.end; while (i < intervals.size() && intervals.get(i).begin <= interval.end) { start = Math.min(start, intervals.get(i).begin); end = Math.max(end, intervals.get(i).end); i++; } // push the merged interval to the result result.add(new Interval(start, end)); } } return result; } public static void main(String[] args) { List<Interval> intervals = List.of(new Interval(1, 5), new Interval(7, 8), new Interval(9, 10), new Interval(12, 15)); Interval interval = new Interval(5, 9); List<Interval> result = mergeIntervals(intervals, interval); System.out.println(result); } } |
Output:
[(1, 10), (12, 15)]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
# A class to store an interval class Interval: def __init__(self, begin, end): self.begin = begin self.end = end def __repr__(self): return str((self.begin, self.end)) def mergeIntervals(intervals, interval): # base case if not intervals: yield interval i = 0 while i < len(intervals): # if the current interval doesn't overlap with the specified interval if intervals[i].end < interval.begin or intervals[i].begin > interval.end: # push current interval to the result yield intervals[i] i = i + 1 else: # if the current interval overlaps with the specified interval, # merge all overlapping intervals into one start, end = interval.begin, interval.end while i < len(intervals) and intervals[i].begin <= interval.end: start, end = min(start, intervals[i].begin), max(end, intervals[i].end) i = i + 1 # push the merged interval to the result yield Interval(start, end) if __name__ == '__main__': intervals = [Interval(1, 5), Interval(7, 8), Interval(9, 10), Interval(12, 15)] interval = Interval(5, 9) result = list(mergeIntervals(intervals, interval)) print(result) |
Output:
[(1, 10), (12, 15)]
We can do the merging in-place without using any other data structure. The idea is to iterate through the intervals and merge the intervals that overlap with the designated interval, removing the intervals that have already been merged in the process. This is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <vector> #include <algorithm> #include <iterator> using namespace std; // Data structure to store an interval struct Interval { int begin, end; }; void mergeIntervals(vector<Interval> &intervals, Interval const &interval) { // skip intervals to the left of the specified interval int i = 0; while (i < intervals.size() && intervals[i].end < interval.begin) { i++; } // merge all intervals that overlap with the specified interval int start = interval.begin, end = interval.end; while (i < intervals.size() && intervals[i].begin <= interval.end) { // update the start and end of the merged interval start = min(start, intervals[i].begin); end = max(end, intervals[i].end); // remove the current interval intervals.erase(intervals.begin() + i); } // insert the merged interval at its correct position intervals.insert(intervals.begin() + i, {start, end}); } int main() { vector<Interval> intervals = { { 1, 5 }, { 7, 8 }, { 9, 10 }, { 12, 15 } }; Interval interval = {5, 9}; mergeIntervals(intervals, interval); for (Interval &interval: intervals) { cout << '{' << interval.begin << ", " << interval.end << "}\n"; } return 0; } |
Output:
{1, 10}
{12, 15}
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
import java.util.ArrayList; import java.util.List; // A class to store an interval class Interval { int begin, end; Interval(int begin, int end) { this.begin = begin; this.end = end; } @Override public String toString() { return "{" + begin + ", " + end + "}"; } } class Main { public static void mergeIntervals(List<Interval> intervals, Interval interval) { // skip intervals to the left of the specified interval int i = 0; while (i < intervals.size() && intervals.get(i).end < interval.begin) { i++; } // merge all intervals that overlap with the specified interval int start = interval.begin; int end = interval.end; while (i < intervals.size() && intervals.get(i).begin <= interval.end) { // update the start and end of the merged interval start = Math.min(start, intervals.get(i).begin); end = Math.max(end, intervals.get(i).end); // remove the current interval intervals.remove(i); } // insert the merged interval at its correct position intervals.add(i, new Interval(start, end)); } public static void main(String[] args) { List<Interval> intervals = new ArrayList<>(List.of( new Interval(1, 5), new Interval(7, 8), new Interval(9, 10), new Interval(12, 15) )); Interval interval = new Interval(5, 9); mergeIntervals(intervals, interval); System.out.println(intervals); } } |
Output:
[(1, 10), (12, 15)]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# A class to store an interval class Interval: def __init__(self, begin, end): self.begin = begin self.end = end def __repr__(self): return str((self.begin, self.end)) def mergeIntervals(intervals, interval): # skip intervals to the left of the specified interval i = 0 while i < len(intervals) and intervals[i].end < interval.begin: i = i + 1 # merge all intervals that overlap with the specified interval start, end = interval.begin, interval.end while i < len(intervals) and intervals[i].begin <= interval.end: # update the start and end of the merged interval start, end = min(start, intervals[i].begin), max(end, intervals[i].end) # remove the current interval intervals.pop(i) # insert the merged interval at its correct position intervals.insert(i, Interval(start, end)) if __name__ == '__main__': intervals = [Interval(1, 5), Interval(7, 8), Interval(9, 10), Interval(12, 15)] interval = Interval(5, 9) mergeIntervals(intervals, interval) print(intervals) |
Output:
[(1, 10), (12, 15)]
The time complexity of the above solution is O(n), where n is the total number of intervals.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)