# Solution For Merge Intervals

Problem statement:
Given a list of intervals, merge overlapping intervals and return the merged intervals in sorted order.

Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, they are merged into [1,6].

Example 2:
Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution:
The problem can be solved using a simple approach of merging intervals which are present next to each other. Here is the high-level algorithm for the problem:

1. Sort the given intervals based on the start element.
2. Create an output list to store the merged intervals.
3. Iterate over the intervals and check if the current interval overlaps with the previous interval.
4. If the intervals overlap, merge them and update the end element of the merged interval.
5. If the intervals do not overlap, add the current interval to the output list.
6. Return the output list.

Let’s implement the above algorithm in Python:

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# Sort the given intervals based on the start element.
intervals = sorted(intervals, key=lambda x: x[0])
# Create an output list to store the merged intervals.
merged_intervals = [] prev_interval = intervals[0] # Iterate over the intervals and merge the overlapping intervals.
for i in range(1, len(intervals)):
current_interval = intervals[i] if prev_interval[1] >= current_interval[0]:
# Merge the current interval with the previous interval.
prev_interval[1] = max(prev_interval[1], current_interval[1])
else:
# Add the previous interval to the merged intervals list.
merged_intervals.append(prev_interval)
prev_interval = current_interval
# Add the last interval to the merged intervals list.
merged_intervals.append(prev_interval)
return merged_intervals

Complexity analysis:
Time complexity: The algorithm runs in O(nlogn) time, where n is the number of intervals. This is because the given intervals are sorted in O(nlogn) time, and the merging process takes place in linear time.
Space complexity: The algorithm runs in O(n) space because we need to store the merged intervals list in the worst case.

## Step by Step Implementation For Merge Intervals

```/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List merge(List intervals) {
// sort interval list by start value
Collections.sort(intervals, new Comparator(){
public int compare(Interval i1, Interval i2){
return i1.start - i2.start;
}
});

// merge intervals
List merged = new ArrayList<>();
for(Interval interval : intervals){
// if list is empty or current interval does not overlap with previous, simply append it
if(merged.isEmpty() || merged.get(merged.size() - 1).end < interval.start){
}
// otherwise, there is overlap, so we update the end of the previous interval if necessary
else{
merged.get(merged.size() - 1).end = Math.max(merged.get(merged.size() - 1).end, interval.end);
}
}
return merged;
}
}```
```# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
# sort the intervals by start time
intervals.sort(key=lambda x: x.start)

# initialize the merged list with the first interval
merged = [intervals[0]]

# go through the rest of the intervals and merge them
for i in range(1, len(intervals)):
# if the current interval overlaps with the previous interval,
# merge them by updating the end time of the previous interval
if intervals[i].start <= merged[-1].end:
merged[-1].end = max(merged[-1].end, intervals[i].end)
# otherwise, add the current interval to the merged list
else:
merged.append(intervals[i])

return merged```
```/**
* Definition for an interval.
* function Interval(start, end) {
*     this.start = start;
*     this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @return {Interval[]}
*/
var merge = function(intervals) {
// sort intervals by start time
intervals.sort((a, b) => a.start - b.start);

// loop through intervals
for (let i = 0; i < intervals.length - 1; i++) {
// check if current interval overlaps with next interval
if (intervals[i].end >= intervals[i + 1].start) {
// merge the two intervals
intervals[i] = new Interval(intervals[i].start, Math.max(intervals[i].end, intervals[i + 1].end));
// remove the next interval from the array
intervals.splice(i + 1, 1);
// decrement i to check the new interval at the current index
i--;
}
}

return intervals;
};```
```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector merge(vector& intervals) {
// sort the intervals by start value
sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b){
return a.start < b.start;
});

// merge intervals
vector merged;
for(auto interval : intervals) {
// if the current interval overlaps with the previous one, merge them
if(!merged.empty() && merged.back().end >= interval.start) {
merged.back().end = max(merged.back().end, interval.end);
}
// otherwise, add the current interval to the result
else {
merged.push_back(interval);
}
}
return merged;
}
};```
```/**
* Definition for an interval.
* public class Interval {
*     public int start;
*     public int end;
*     public Interval() { start = 0; end = 0; }
*     public Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public IList Merge(IList intervals) {
// check for edge cases
if (intervals == null || intervals.Count <= 1) {
return intervals;
}

// sort the intervals by start time
intervals = intervals.OrderBy(i => i.start).ToList();

// initialize merged list
List merged = new List();

// track the interval with the earliest start time
Interval first = intervals[0];

// go through the rest of the intervals
for (int i = 1; i < intervals.Count; i++) {
Interval current = intervals[i];

// if the current interval overlaps with the first interval,
// update the end time of the first interval if necessary
if (current.start <= first.end) {
first.end = Math.Max(first.end, current.end);
}
// otherwise, there is no overlap, so add the first interval
// to the merged list and update first to be the current interval
else {
first = current;
}
}

// add the last interval to the merged list