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){
                merged.add(interval);
            }
            // 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 {
                merged.Add(first);
                first = current;
            }
        }
        
        // add the last interval to the merged list
        merged.Add(first);
        
        return merged;
    }
}