### Problem Statement

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

### Example:

```Input 1: intervals: [[1,4], [7,9], [2,5]]
Output 1: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into one [1,5].

Input 2: intervals: [[2,4], [3,8], [7,12]]
Output 2: [[2,12]]
Explanation: Since all interval overlaps, merge all into one, [1, 6].```

### Code

```import java.util.*;

class MergeIntervals {

public static List<Interval> merge(List<Interval> intervals) {
if (intervals.size() < 2)
return intervals;

// sort the intervals by start time
Collections.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));

Iterator<Interval> intervalItr = intervals.iterator();
Interval interval = intervalItr.next();
int start = interval.start;
int end = interval.end;

while (intervalItr.hasNext()) {
interval = intervalItr.next();
if (interval.start <= end) { // overlapping intervals, adjust the 'end'
end = Math.max(interval.end, end);
} else { // non-overlapping interval, add the previous interval and reset
start = interval.start;
end = interval.end;
}
}

return mergedIntervals;
}

public static void main(String[] args) {
List<Interval> input = new ArrayList<Interval>();
System.out.print("Merged intervals: ");
for (Interval interval : MergeIntervals.merge(input))
System.out.print("[" + interval.start + "," + interval.end + "] ");
System.out.println();

input = new ArrayList<Interval>();
System.out.print("Merged intervals: ");
for (Interval interval : MergeIntervals.merge(input))
System.out.print("[" + interval.start + "," + interval.end + "] ");
System.out.println();
}
}

class Interval {
int start;
int end;

public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}```
```using namespace std;

#include <algorithm>
#include <iostream>
#include <vector>

class Interval {
public:
int start = 0;
int end = 0;

Interval(int start, int end) {
this->start = start;
this->end = end;
}
};

class MergeIntervals {
public:
static vector<Interval> merge(vector<Interval> &intervals) {
if (intervals.size() < 2) {
return intervals;
}

// sort the intervals by start time
sort(intervals.begin(), intervals.end(),
[](const Interval &x, const Interval &y) { return x.start < y.start; });

vector<Interval> mergedIntervals;

vector<Interval>::const_iterator intervalItr = intervals.begin();
Interval interval = *intervalItr++;
int start = interval.start;
int end = interval.end;
while (intervalItr != intervals.end()) {
interval = *intervalItr++;
if (interval.start <= end) {  // overlapping intervals, adjust the 'end'
end = max(interval.end, end);
} else {  // non-overlapping interval, add the previous interval and reset
mergedIntervals.push_back({start, end});
start = interval.start;
end = interval.end;
}
}
mergedIntervals.push_back({start, end});
return mergedIntervals;
}
};

int main(int argc, char *argv[]) {
vector<Interval> input = {{1,4}, {7,9}, {2,5}};
cout << "Merged intervals: ";
for (auto interval : MergeIntervals::merge(input)) {
cout << "[" << interval.start << "," << interval.end << "] ";
}
cout << endl;

input = {{2,4}, {3,8}, {7,12}};
cout << "Merged intervals: ";
for (auto interval : MergeIntervals::merge(input)) {
cout << "[" << interval.start << "," << interval.end << "] ";
}
cout << endl;
}```
```from __future__ import print_function

class Interval:
def __init__(self, start, end):
self.start = start
self.end = end

def print_interval(self):
print("[" + str(self.start) + ", " + str(self.end) + "]", end='')

def merge(intervals):
if len(intervals) < 2:
return intervals

# sort the intervals on the start time
intervals.sort(key=lambda x: x.start)

mergedIntervals = []
start = intervals[0].start
end = intervals[0].end
for i in range(1, len(intervals)):
interval = intervals[i]
if interval.start <= end:  # overlapping intervals, adjust the 'end'
end = max(interval.end, end)
else:  # non-overlapping interval, add the previous interval and reset
mergedIntervals.append(Interval(start, end))
start = interval.start
end = interval.end

mergedIntervals.append(Interval(start, end))
return mergedIntervals

def main():
print("Merged intervals: ", end='')
for i in merge([Interval(1, 4), Interval(7, 9), Interval(2, 5)]):
i.print_interval()
print()

print("Merged intervals: ", end='')
for i in merge([Interval(2, 4), Interval(3, 8), Interval(7, 12)]):
i.print_interval()
print()

main()```

### Output:

```Merged intervals: [1,5] [7,9]
Merged intervals: [2,12]```

### Time and Space Complexity

Time Complexity: We performed sorting to sort the intervals list based on the start value O(nlogn) and then we traversed the complete list for merging intervals in O(n) . So, Overall time complexity is O(nlogn).

Space Complexity: O(N), Since we are returning a new list of merged intervals.