# Given a collection of intervals, merge all overlapping intervals.

For example

Given `[1,3],[2,6],[8,10],[15,18]`

should return `[1,6],[8,10],[15,18]`

It is one of my favorite question to ask in an interview. The `tuple` has start and and end element. To merge two tuple at `i-1th` and `ith` index, following condition should be true:

`start element at ith <= end element at i-1th`
• Sort the list.
• Put the first element in the new list
• check the top element of the new list with the ith index of the input array
• If the condition is true `start element at ith <= end element at i-1th`
• Merge the top of the element in the list with the ith index element
• Otherwise, insert the element on top of the list
``````public class MergeInterval {

public static void main(String[] args) {
List l = new ArrayList();
System.out.println(new MergeInterval().merge(l));

}

public List merge(List intervals) {
if (intervals != null && intervals.size() == 0) {
return Collections.EMPTY_LIST;
}
Collections.sort(intervals, new Comparator() {

@Override
public int compare(Interval o1, Interval o2) {
if(o1.start > o2.start) {
return 1;
} else if (o1.start < o2.start) {
return -1;
}
return 0;
}
});
List list = new ArrayList();
for(int i=1; i < intervals.size(); i++) {
Interval interval = list.get(list.size() - 1);
Interval curr = intervals.get(i);
if (curr.start <= interval.end) {
interval.start = Math.min(interval.start, curr.start);
interval.end = Math.max(interval.end, curr.end);
} else {
}
}
return list;
}

static class Interval {
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
}
}
``````