Merge Overlapping Intervals

In this post, we are going to solve a problem merge overlapping intervals.

Given a list of time intervals. Each interval has a start and end time. Write a code to merge all overlapping intervals. The given intervals may or may not be sorted.

For example –

Example 1-

Input: [[1,4], [2,5], [6,9]] Output: [[1,5], [6,9]]

Example 2-

Input: [[7,8], [2,3], [5,9]] Output: [[2,3], [5,9]]

Example 3-

Input: [[1,4], [2,6], [3,5]] Output: [[1,6]]

We have discussed the problem statement. Now, let’s think how we can solve this problem. What’s the time and space complexity of our solution?

Programming video tutorials

Find Top k most frequent elements

Merge Overlapping Intervals – Java Code

In this problem, Given a collection of intervals, we have to merge all overlapping intervals.

Let’s first understand the algorithm to solve the merge intervals problem and then we will write its java code.

1) Sort all intervals in increasing order of start time.

2) Once all the intervals are sorted. The next step is to traverse the sorted intervals starting from the first interval and do the following steps for every interval.

a) If the current interval is not the first interval and it overlaps with the previous interval (i.e. b.start <= a.end). In that case, merge the current interval with the previous interval. Keep doing it while the interval overlaps with the previous one.

b) Else add the current interval to the output list of intervals.

3) When all the intervals are traversed, return the output list.

The time complexity of this approach is O(nlogn). The space complexity of this approach is O(1).

//Interval class
class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
//Merge intervals
public class MergeIntervals {
public static List<Interval> mergeInterval(List<Interval> intervals) {
/*
If list has less than two elements,
then there is nothing to merge
*/
if(intervals.size() < 2) {
return intervals;
}
List<Interval> output = new ArrayList<>();
//Sort the interval on the basis of start attribute
Collections.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));
//Take interval present at 0th element
Interval temp = intervals.get(0);
int start = temp.start;
int end = temp.end;
//Traverse a list
for(int i = 1; i < intervals.size(); i++) {
temp = intervals.get(i);
if(temp.start <= end) {
end = Math.max(end, temp.end);
} else {
output.add(new Interval(start, end));
start = temp.start;
end = temp.end;
}
}
output.add(new Interval(start, end));
return output;
}
public static void main(String[] args) {
List<Interval> input = new ArrayList<>();
input.add(new Interval(1, 4));
input.add(new Interval(2, 5));
input.add(new Interval(6, 9));
List<Interval> output = mergeInterval(input);
for(Interval result : output) {
System.out.println(result.start + " " + result.end);
}
}
}

//Interval class

class Interval {

int start;

int end;

public Interval(int start, int end) {

this.start = start;

this.end = end;

}

//Merge intervals

public class MergeIntervals {

public static List<Interval> mergeInterval(List<Interval> intervals) {

If list has less than two elements,

then there is nothing to merge

if(intervals.size() < 2) {

return intervals;

}

List<Interval> output = new ArrayList<>();

//Sort the interval on the basis of start attribute

Collections.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));

//Take interval present at 0th element

Interval temp = intervals.get(0);

int start = temp.start;

int end = temp.end;

//Traverse a list

for(int i = 1; i < intervals.size(); i++) {

temp = intervals.get(i);

if(temp.start <= end) {

end = Math.max(end, temp.end);

} else {

output.add(new Interval(start, end));

start = temp.start;

end = temp.end;

}

output.add(new Interval(start, end));

return output;

}

public static void main(String[] args) {

List<Interval> input = new ArrayList<>();

input.add(new Interval(1, 4));

input.add(new Interval(2, 5));

input.add(new Interval(6, 9));

List<Interval> output = mergeInterval(input);

for(Interval result : output) {

System.out.println(result.start + " " + result.end);

}

Merge Overlapping Intervals InterviewBit Solution – Java Code

I have already explained the logic to solve this problem. Let’s write its code.

//InterviewBit Solution
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
//Declare an array
ArrayList<Interval> result = new ArrayList<>();
//Sort all intervals based on increasing order of time
Collections.sort(intervals,(a, b) -> Integer.compare(a.start, b.start));
Interval temp = intervals.get(0);
int start = temp.start;
int end = temp.end;
for(int i = 1; i < intervals.size(); i++) {
temp = intervals.get(i);
if(temp.start <= end) {
end = Math.max(end, temp.end);
} else {
result.add(new Interval(start, end));
start = temp.start;
end = temp.end;
}
}
result.add(new Interval(start,end));
return result;
}
}

//InterviewBit Solution

public class Solution {

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

//Declare an array

ArrayList<Interval> result = new ArrayList<>();

//Sort all intervals based on increasing order of time

Collections.sort(intervals,(a, b) -> Integer.compare(a.start, b.start));

Interval temp = intervals.get(0);

int start = temp.start;

int end = temp.end;

for(int i = 1; i < intervals.size(); i++) {

temp = intervals.get(i);

if(temp.start <= end) {

end = Math.max(end, temp.end);

} else {

result.add(new Interval(start, end));

start = temp.start;

end = temp.end;

}

result.add(new Interval(start,end));

return result;

}

Video Tutorial

In this video tutorial, I have explained an approach to merge intervals.

Merge Overlapping intervals Video Tutorial

Merge Overlapping Intervals Video Tutorial

0 Shares

Merge Overlapping Intervals – Java Code

Merge Overlapping Intervals InterviewBit Solution – Java Code

Video Tutorial

About WebRewrite

Related Posts (YARPP)

Topics

String

Linked List

Binary Tree

Hash Map

Java

Queue

Stack

Binary Search

Programming

Sliding Window

Composer

Memcache

Javascript

Cookie

Merge Overlapping Intervals

Merge Overlapping Intervals – Java Code

Merge Overlapping Intervals InterviewBit Solution – Java Code

Video Tutorial

Related posts:

About WebRewrite

Related Posts (YARPP)

Topics

String

Linked List

Binary Tree

Hash Map

Java

Queue

Stack

Binary Search

Programming

Sliding Window

Composer

Memcache

Javascript

Cookie