Merge Intervals

                                            
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.empty()){
            return {};
        }
        
        sort(intervals.begin(), intervals.end());
        
        vector<vector<int>> res;
        res.push_back(intervals[0]);
        
        for(int i = 1; i < intervals.size(); i++){
            if(intervals[i][0] <= res.back()[1]){
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            } else {
                res.push_back(intervals[i]);
            }
        }
        
        return res;
    }
};

                                            
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        List<int[]> result = new ArrayList<>();
        int[] currentInterval = intervals[0];
        result.add(currentInterval);
        
        for (int[] interval : intervals) {
            if (interval[0] <= currentInterval[1]) {
                currentInterval[1] = Math.max(currentInterval[1], interval[1]);
            } else {
                currentInterval = interval;
                result.add(currentInterval);
            }
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

                                            
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        intervals.sort(key=lambda x: x[0])
        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

                                            
public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals.Length <= 1) {
            return intervals;
        }
        
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        
        List<int[]> result = new List<int[]>();
        int[] currentInterval = intervals[0];
        result.Add(currentInterval);
        
        foreach (var interval in intervals) {
            int currentEnd = currentInterval[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];
            
            if (currentEnd >= nextStart) {
                currentInterval[1] = Math.Max(currentEnd, nextEnd);
            } else {
                currentInterval = interval;
                result.Add(currentInterval);
            }
        }
        
        return result.ToArray();
    }
}

                                            
function merge(intervals: number[][]): number[][] {
    if (intervals.length <= 1) {
        return intervals;
    }
    
    intervals.sort((a, b) => a[0] - b[0]);
    
    const result: number[][] = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const lastInterval = result[result.length - 1];
        const currentInterval = intervals[i];
        
        if (currentInterval[0] <= lastInterval[1]) {
            lastInterval[1] = Math.max(lastInterval[1], currentInterval[1]);
        } else {
            result.push(currentInterval);
        }
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[][] $intervals
     * @return Integer[][]
     */
    function merge($intervals) {
        if (count($intervals) == 0) {
            return [];
        }
        
        usort($intervals, function($a, $b) {
            return $a[0] - $b[0];
        });
        
        $result = [];
        $current = $intervals[0];
        
        for ($i = 1; $i < count($intervals); $i++) {
            if ($current[1] >= $intervals[$i][0]) {
                $current[1] = max($current[1], $intervals[$i][1]);
            } else {
                $result[] = $current;
                $current = $intervals[$i];
            }
        }
        
        $result[] = $current;
        
        return $result;
    }
}

                                            
class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        var sortedIntervals = intervals.sorted { $0[0] < $1[0] }
        var result = [[Int]]()
        
        for interval in sortedIntervals {
            if result.isEmpty || interval[0] > result.last![1] {
                result.append(interval)
            } else {
                result[result.count - 1][1] = max(result.last![1], interval[1])
            }
        }
        
        return result
    }
}

                                            
class Solution {
    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        if (intervals.isEmpty()) {
            return emptyArray()
        }
        
        intervals.sortBy { it[0] }
        
        val result = mutableListOf<IntArray>()
        var currentInterval = intervals[0]
        
        for (i in 1 until intervals.size) {
            val interval = intervals[i]
            if (interval[0] <= currentInterval[1]) {
                currentInterval[1] = maxOf(currentInterval[1], interval[1])
            } else {
                result.add(currentInterval)
                currentInterval = interval
            }
        }
        
        result.add(currentInterval)
        
        return result.toTypedArray()
    }
}

                                            
class Solution {
  List<List<int>> merge(List<List<int>> intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    
    List<List<int>> merged = [];
    
    for (List<int> interval in intervals) {
      if (merged.isEmpty || merged.last[1] < interval[0]) {
        merged.add(interval);
      } else {
        merged.last[1] = interval[1] > merged.last[1] ? interval[1] : merged.last[1];
      }
    }
    
    return merged;
  }
}

                                            
func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return [][]int{}
    }

    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    result := make([][]int, 0)
    currentInterval := intervals[0]

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] <= currentInterval[1] {
            currentInterval[1] = max(currentInterval[1], intervals[i][1])
        } else {
            result = append(result, currentInterval)
            currentInterval = intervals[i]
        }
    }

    result = append(result, currentInterval)

    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Integer[][]} intervals
# @return {Integer[][]}
def merge(intervals)
    intervals.sort_by! { |interval| interval[0] }
    result = [intervals[0]]
    
    for i in 1..intervals.length-1
        current_interval = intervals[i]
        last_merged_interval = result.last
        
        if current_interval[0] <= last_merged_interval[1]
            last_merged_interval[1] = [last_merged_interval[1], current_interval[1]].max
        else
            result << current_interval
        end
    end
    
    return result
end

                                            
object Solution {
    def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
        intervals.sortBy(_(0)).foldLeft(List[Array[Int]]()) { (result, interval) =>
            result match {
                case Nil => List(interval)
                case head :: tail if interval(0) <= head(1) =>
                    head(1) = Math.max(head(1), interval(1))
                    result
                case _ => interval :: result
            }
        }.reverse.toArray
    }
}

                                            
impl Solution {
    pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut intervals = intervals;
        intervals.sort_by_key(|interval| interval[0]);
        
        let mut result: Vec<Vec<i32>> = Vec::new();
        
        for interval in intervals {
            if result.is_empty() || result.last().unwrap()[1] < interval[0] {
                result.push(interval);
            } else {
                result.last_mut().unwrap()[1] = result.last().unwrap()[1].max(interval[1]);
            }
        }
        
        result
    }
}

To solve this coding challenge, we need to merge overlapping intervals from the given list of intervals. The concept behind the solution is pretty intuitive if you break down the problem into smaller steps. Below, I will provide a step-by-step detailed explanation and pseudocode on how to achieve the desired result.

Explanation

Understanding the Problem :

We are given a list of intervals. An interval is represented as a pair of integers, where the first integer signifies the start of the interval, and the second integer signifies the end.
Our task is to merge any overlapping intervals. Two intervals overlap if the end of one is equal to or greater than the start of the next.

Sorting the Intervals :

To efficiently identify overlapping intervals, we first need to sort the list of intervals by their start time. Sorting ensures that any overlapping intervals will be adjacent to each other in the list.

Iterating and Merging Intervals :

After sorting the intervals, we iterate through the list.
We keep a new list called
merged

to store our merged intervals.
For each interval, we check if it overlaps with the last interval in the
merged

list.
If it overlaps, we merge the current interval with the last interval in the
merged

list.
If it does not overlap, we simply append the current interval to the
merged

list.

Returning the Result :

After iterating through all the intervals and merging as needed, the
merged

list will contain the non-overlapping intervals covering all input intervals.

Step-by-Step Explanation / Detailed Steps in Pseudocode

Step 1: Input Validation : Check if the list of intervals is empty. If it is, return an empty list because there are no intervals to merge.
Step 2: Sorting : Sort the list of intervals by their starting times. This is important to ensure that we can easily compare each interval with the next one.
Step 3: Initialization : Initialize an empty list called
merged

to store the merged intervals.
Step 4: Loop through the Intervals :

For each interval in the sorted list of intervals:
If the
merged

list is empty (i.e., we are adding the first interval) or if the last interval in the
merged

list does not overlap with the current interval, add the current interval to the
merged

list.
If the last interval in the
merged

list overlaps with the current interval, merge them by updating the end time of the last interval in
merged

to be the maximum of the end times of the overlapping intervals.

Step 5: Return the Merged Intervals : The
merged

list now contains all the non-overlapping intervals that cover all input intervals.

Pseudocode

                                            
# Function to merge overlapping intervals
function mergeIntervals(intervals):

    # Step 1: Check if intervals list is empty
    if intervals is empty:
        return an empty list

    # Step 2: Sort the intervals by their starting times
    sort intervals by the first element of each interval
    
    # Step 3: Initialize the list to store merged intervals
    merged = empty list
    
    # Step 4: Loop over each interval in the sorted list
    for interval in intervals:
        
        # If merged list is empty or no overlap, simply append the interval
        if merged is empty or merged[-1][1] < interval[0]:
            append interval to merged
        
        # Otherwise, there's an overlap, so merge the current interval
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    # Step 5: Return the merged intervals
    return merged

# Example Usage
input_intervals = [[1,3],[2,6],[8,10],[15,18]]
output_intervals = mergeIntervals(input_intervals)
# Output should be: [[1,6],[8,10],[15,18]]

In this pseudocode:

intervals

represents the list of input intervals.
merged[-1]

accesses the last element in the
merged

list.
max(a, b)

is a function that returns the greater of
a

and
b

.

This approach ensures that all overlapping intervals are merged efficiently. The use of sorting followed by a single pass through the list gives an optimal time complexity of O(n log n) due to the sorting step, which is very efficient for this problem.