DSA Merge Intervals: Explanation & Solution

Last update on May 16 2024 10:09:33 (UTC/GMT +8 hours)

Merge Intervals:

Given a collection of intervals, merge any overlapping intervals.

Problem Statement

Introduction to the Problem
Underlying Concepts
Brute Force Approach
Optimization Techniques
Algorithmic Thinking
Common Mistakes and Pitfalls
Coding Best Practices
Testing and Debugging
Algorithm Analysis
Application in Real-world Projects
Solution for different languages
Time and Space Complexity

Introduction to the Problem

Problem Statement:

The "Merge Intervals" problem involves merging overlapping intervals within a collection of intervals.
Given a set of intervals represented as pairs [start, end], the goal is to merge any overlapping intervals to create a new set of non-overlapping intervals.
Input and output requirements:

Input: The input consists of a collection of intervals, where each interval is represented as a pair of integers [start, end].
Output: The output is a new set of intervals where any overlapping intervals have been merged into a single interval.

Real-world Scenario:

Provide a Simple Real-World Scenario:

For example, suppose a clinic has multiple appointments scheduled throughout the day. Some appointments may overlap with each other, especially if they run longer than expected or if multiple patients arrive simultaneously.
To optimize the clinic's schedule and avoid conflicts, it's necessary to merge overlapping appointment intervals into contiguous time slots. This ensures efficient use of resources and avoids double-booking or gaps in the schedule.

Underlying Concepts:

Intervals:

Concept of intervals

Intervals represent a range of values between a "start point" and an "end point".
In the context of the problem, intervals are typically represented as pairs [start, end], where start and end are integers representing the beginning and ending points of the interval respectively.
For example, an interval [1, 3] represents all values from 1 to 3.

Overlapping intervals:

Intervals to overlap and identify overlapping intervals

Intervals overlap if they share some common part of their ranges.
Two intervals [a, b] and [c, d] overlap if and only if (a <= d) and (b >= c).
To identify overlapping intervals in a collection, iterate through each interval and compare it with every other interval to determine if there is any overlap.

Sorting:

Sorting intervals based on their Start or End times for efficient merging:

Sorting intervals based on their start or end times is crucial for efficiently merging overlapping intervals.
Sorting by start times ensures that intervals with earlier start times are processed first, facilitating the merging process.
Sorting by end times can also be beneficial, especially when there are many intervals starting at the same point. This allows for efficient identification of the end of overlapping intervals.
By sorting the intervals, we can streamline the merging process and improve the overall efficiency of the solution.

Brute Force Approach:

Naive Solution:

Brute Force Solution - Iterates through each Pair of intervals to check for overlap and merge if necessary:

The naive solution involves checking every possible pair of intervals to see if they overlap and merging them if they do.
Here’s a step-by-step outline of the naive approach:

Initialization: Start with an empty list to store the merged intervals.
Comparison: For each interval, compare it with every other interval to check if they overlap.
Merging: If two intervals overlap, merge them into a single interval by taking the minimum start and the maximum end of the overlapping intervals.
Update: Replace the original intervals with the merged interval and continue checking for further overlaps.
Result: Continue this process until no more overlapping intervals can be merged.

This approach ensures that all overlapping intervals are merged, but it is not efficient for large collections of intervals.

Complexity Analysis:

Time and Space complexity of the Brute Force approach and Its limitations:

Time Complexity:

The "Brute force" approach involves nested loops where each interval is compared with every other interval.
This results in a time complexity of O(n2), where 𝑛n is the number of intervals.
Each comparison involves checking if two intervals overlap and potentially merging them, leading to quadratic time complexity.

Space Complexity:

The space complexity is O(n) in the worst case, as we might end up storing all the intervals without any merging if none overlap.
Additional space is used to store the merged intervals and possibly intermediate results during the merging process.

Limitations:

The "Brute force" approach is inefficient for large datasets due to its quadratic time complexity.
It becomes computationally expensive and slow as the number of intervals increases.

Example of Naive Solution in Pseudocode

function mergeIntervals(intervals):
    merged = []
    while intervals is not empty:
        current = intervals[0]
        intervals.remove(current)
        for each interval in intervals:
            if current overlaps with interval:
                current = merge(current, interval)
                intervals.remove(interval)
        merged.add(current)
    return merged

function merge(interval1, interval2):
    start = min(interval1.start, interval2.start)
    end = max(interval1.end, interval2.end)
    return [start, end]

Optimization Techniques

Sorting and Merging:

Sorting the intervals by their start times helps to simplify the process of merging because it ensures that we only need to look at consecutive intervals to check for overlaps.
When intervals are sorted by their start times, any overlapping intervals will appear next to each other in the sorted list. This allows us to efficiently merge them in a single pass through the list.
Sorting the intervals ensures that once an interval ends, no subsequent intervals can start before it, thereby limiting the comparison to only adjacent intervals.

Linear Scan Approach that Merges Intervals in a Single Pass Through the Sorted List:

Here’s a step-by-step outline of the optimized approach:

Initialization: Start by sorting the list of intervals based on their start times.
Start Merging: Initialize a new list to store merged intervals and add the first interval to this list.
Iterate: Iterate through the sorted intervals and compare the current interval with the last interval in the merged list.
Check for overlap:

If the current interval overlaps with the last merged interval (i.e., the start of the current interval is less than or equal to the end of the last merged interval), merge them by updating the end of the last merged interval to be the maximum of the end times of both intervals.
If there is no overlap, add the current interval to the merged list as a new interval.

Continue Until Done: Repeat the process for all intervals in the sorted list.
Result: The merged list now contains all merged intervals with no overlaps.

Pseudocode for Optimized Approach

function mergeIntervals(intervals):
    if intervals is empty:
        return []
    
    // Sort intervals by start time
    intervals.sort by interval.start
    
    // Initialize merged list with the first interval
    merged = [intervals[0]]
    
    // Iterate through the sorted intervals
    for i from 1 to length(intervals) - 1:
        current = intervals[i]
        lastMerged = merged[-1]
        
        if current.start <= lastMerged.end:
            // Merge the intervals
            lastMerged.end = max(lastMerged.end, current.end)
        else:
            // No overlap, add current interval to merged list
            merged.append(current)
    
    return merged

Compare the Time and Space Complexity of the Optimized approach with the Brute Force approach:

Time complexity:

The time complexity of the optimized approach is dominated by the sorting step, which is (𝑛log 𝑛), where 𝑛 is the number of intervals.
The subsequent linear scan through the sorted intervals takes (n) time.
Therefore, the overall time complexity of the optimized approach is (𝑛log 𝑛).
This is significantly better than the brute force approach, which has a time complexity (n2).

Space complexity:

The space complexity of the optimized approach is (𝑛) for storing the merged intervals.
Sorting the intervals can be done in place (if using a language or sorting algorithm that supports in-place sorting), which means no additional space is required for the sorting step.
The overall space complexity is (𝑛), which is similar to the brute force approach. However, the optimized approach is more efficient in terms of processing time.

Visualization:

Data Structure: DSA Merge Intervals algorithms

Algorithmic Thinking:

Greedy Strategy:

A greedy strategy makes a series of choices, each of which looks the best at the moment, to find an optimal solution. For interval problems, this means making local optimizations at each step to build towards the overall solution.
Application to Merging Intervals: In the context of merging intervals, the greedy strategy involves sorting the intervals and then iterating through them to merge overlapping intervals as soon as they are detected. This approach ensures that we always have the current best (i.e., merged) intervals without needing to backtrack.
Step-by-Step Process:

Sort Intervals: First, sort the intervals by their start times. This ensures that any overlapping intervals are adjacent in the sorted list.
Merge Overlapping Intervals: Initialize a list to store the merged intervals and add the first interval to it. Then, for each subsequent interval, check if it overlaps with the last interval in the merged list. If it does, merge them. If it does not, add the new interval to the merged list.

Optimality: By always merging intervals as soon as they overlap, the greedy strategy ensures that we are making the best local choice at each step. This leads to a globally optimal solution where all overlapping intervals are merged efficiently.

Algorithmic Strategies:

Concept of Greedy Algorithms: Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. This approach is particularly effective for interval-related problems where local decisions (e.g., merging intervals) lead directly to the global solution.
Advantages of Greedy Strategy in Interval Problems:

Simplicity: Greedy algorithms are often simpler and easier to implement compared to other strategies like dynamic programming or backtracking.
Efficiency: Greedy algorithms can provide efficient solutions with optimal time complexity, especially when the problem can be broken down into a series of local optimization steps.

Examples of Interval-related Problems Solved by Greedy Approach:

Activity Selection Problem: Selecting the maximum number of non-overlapping intervals (activities) that can be performed by a single person.
Meeting Rooms Problem: Finding the minimum number of meeting rooms required to accommodate all given intervals (meetings).

Key Insight: The key insight in using a greedy approach for interval problems is that by sorting the intervals and making local merging decisions, we can construct the optimal solution in an efficient and straightforward manner.

Example of Greedy Strategy:

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

Sort the Intervals:

Sorted intervals: [[1, 3], [2, 6], [8, 10], [15, 18]] (already sorted in this case)

Initialize the Merged List:

Merged list: [[1, 3]]

Iterate and Merge:

Compare [2, 6] with [1, 3]: They overlap, so merge to [1, 6]

Merged list: [[1, 6]]

Compare [8, 10] with [1, 6]: No overlap, add [8, 10]

Merged list: [[1, 6], [8, 10]]

Compare [15, 18] with [8, 10]: No overlap, add [15, 18]

Merged list: [[1, 6], [8, 10], [15, 18]]

Common Mistakes and Pitfalls:

Incorrect Overlapping Check:

Discuss Potential Mistakes in implementing the overlapping check condition:

Misunderstanding the overlap condition: One common mistake is incorrectly implementing the condition to check if two intervals overlap. The correct condition for two intervals [a, b] and [c, d] to overlap is c <= b and a <= d. If either condition fails, the intervals do not overlap.
Off-by-One Errors: Developers might incorrectly use strict inequalities (< or >) instead of non-strict inequalities (<= or >=). For example, using c < b instead of c <= b might fail to merge intervals that just touch each other.
Merging Logic: Another potential mistake is merging intervals without correctly updating the end time of the merged interval. Ensure the merged interval's end time is the maximum of the overlapping intervals' end times.

Handling Edge Cases:

Issues related to "Edge Cases", such as empty input or single intervals:

Empty Input: Ensure that the function handles the case where the input list is empty. The function should return an empty list in this case.
Single Interval: The function should correctly handle the case where the input list contains only one interval. The output should be the same single interval since there is nothing to merge.
Intervals with Zero Length: Intervals where the start and end times are the same might cause confusion. Ensure that the implementation treats these intervals correctly.
Already Merged Intervals: If the input list contains intervals that are already merged or do not overlap, the function should return them as they are.
Overlapping at Boundaries: Intervals that overlap exactly at their boundaries should be correctly identified and merged.

Coding Best Practices:

Modularity:

Emphasize the importance of writing modular code for "Sorting and Merging Intervals":

Separation of Concerns: Break down the problem into smaller, manageable functions.
For example, separate the sorting of intervals from the merging logic. This makes the code easier to understand, test, and maintain.
Reusability: By creating modular functions, you can reuse these functions in other parts of your code or in different projects. For instance, a sorting function can be reused wherever interval sorting is needed.
Testing: Modular code is easier to test. You can test each function independently to ensure it works correctly before integrating it into the larger program.

Variable Naming:

Meaningful Variable Names for Better Code Readability:

Clarity: Use variable names that clearly describe their purpose. This makes the code more readable and easier to understand. Avoid single-letter names except for loop counters or indices.
Consistency: Stick to a consistent naming convention throughout your code. For example, use 'snake_case' for variables and functions in Python.
Descriptive Names: Choose descriptive names for variables that convey their role.
For example, use 'current_interval' instead of 'ci' and 'last_merged_interval' instead of 'lmi'.

Testing and Debugging:

Test Cases:

Basic Test Case: Verify that the function works for a basic set of intervals.
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] # Expected output: [[1, 6], [8, 10], [15, 18]]
Non-Overlapping Intervals: Test with intervals that do not overlap at all.
intervals = [[1, 2], [3, 4], [5, 6]] # Expected output: [[1, 2], [3, 4], [5, 6]]
Partially Overlapping Intervals: Test with intervals that overlap partially.
intervals = [[1, 4], [2, 5], [7, 9]] # Expected output: [[1, 5], [7, 9]]
Fully Overlapping Intervals: Test with intervals where one interval completely overlaps another.
intervals = [[1, 10], [2, 6], [8, 10]] # Expected output: [[1, 10]]
Single Interval: Test with only one interval.
intervals = [[1, 3]] # Expected output: [[1, 3]]
Empty Input: Test with an empty list of intervals.
intervals = [] # Expected output: []

Debugging Techniques:

Print Statements: Use print statements to track the values of key variables such as 'current_interval', 'last_merged_interval', and the 'merged_intervals' list during each iteration of the loop.
Edge Case Handling: Ensure that edge cases are properly handled by writing specific test cases and checking the function's behavior for these cases.
Example: An empty list of intervals.
assert merge_intervals([]) == []

Example: A single interval.
assert merge_intervals([[1, 3]]) == [[1, 3]]

Step-by-Step Debugging: Use a debugger to step through each line of the code. Check the state of variables at each step to understand the flow and identify where things might be going wrong.

Python Debugger (pdb):

Boundary Value Testing: Test intervals that lie on the boundaries of typical values, such as the maximum and minimum values in the dataset.
intervals = [[-1000000, -999999], [1000000, 1000001]]
Expected output: [[-1000000, -999999], [1000000, 1000001]]

Algorithm Analysis:

Time and Space Complexity:

Time Complexity:

The first step in the optimized merging intervals approach is to sort the intervals based on their start times. Sorting an array of length 𝑛n has a time complexity of (𝑛log 𝑛) .
After sorting, the algorithm performs a single pass through the intervals to merge them. This pass involves iterating through the list once, which has a time complexity of (𝑛).
Therefore, the overall time complexity of the optimized solution is dominated by the sorting step, making it (𝑛log 𝑛)+𝑂(𝑛) = 𝑂(𝑛log 𝑛).

Space Complexity:

The space complexity of the algorithm depends on the additional space used for storing the merged intervals and any auxiliary space required for sorting.
Sorting in-place uses (1) additional space for the sorting step, assuming we don't count the input list itself.
The merged intervals list will store up to 𝑛n intervals in the worst case, where no intervals overlap. This requires (𝑛) space.
Therefore, the overall space complexity is (𝑛).

Trade-offs:

Time Complexity Trade-offs:

Optimized Approach (Sorting and Merging): The optimized approach has a time complexity of (𝑛log 𝑛) due to the sorting step. This is efficient and acceptable for most practical purposes, especially when 𝑛n is large.
Brute Force Approach: In contrast, a brute force approach that checks every pair of intervals to see if they overlap and merges them has a much higher time complexity of (𝑛2). This becomes impractical as 𝑛 grows.

Space Complexity Trade-offs:

In-place Sorting: Using an in-place sorting algorithm helps keep the space complexity low, at (1) additional space for the sorting step.
Auxiliary Data Structures: If additional data structures, such as auxiliary arrays or lists, are used to store intermediate results, the space complexity may increase. However, the overall space complexity is still (𝑛), since storing the merged intervals requires 𝑂(𝑛) space.
Balancing Time and Space: When optimizing algorithms, a common trade-off involves balancing time and space complexity. For the "Merge Intervals" problem, the optimized approach achieves a good balance by using (𝑛log⁡𝑛) time and 𝑂(𝑛) space. This is generally considered efficient for this type of problem.

Example of Trade-offs:

If the input size 𝑛 is very large and the sorting step becomes a bottleneck, one could consider parallel sorting algorithms to reduce wall-clock time at the cost of additional complexity and potentially higher space usage.
In scenarios where memory is limited, it might be necessary to use in-place operations and carefully manage memory usage to stay within acceptable bounds.

Application in Real-world Projects:

Scheduling Algorithms:

In many scheduling algorithms, tasks or events are represented by intervals. Merging overlapping intervals can help in optimizing schedules, avoiding conflicts, and ensuring efficient resource utilization.
For example, in job scheduling on a single machine, overlapping job times can be merged to determine the total busy time of the machine.

Calendar Management Systems:

Calendar applications often need to merge overlapping meeting times to provide a clear view of available and busy slots.
For instance, in a shared calendar system, combining overlapping meeting requests helps in displaying the correct availability status for the participants.

Resource Allocation:

In systems that allocate resources based on time intervals (e.g., booking systems for conference rooms or equipment), merging intervals ensures that resources are optimally allocated without double booking.
For example, merging overlapping booking slots in a hotel reservation system can help in maximizing room utilization.

Data Analysis:

In data analysis, intervals can represent periods of activity or events. Merging these intervals helps in simplifying data and drawing meaningful insights.
For example, merging overlapping time periods of sensor data can help in identifying continuous activity periods.

Networking:

In networking, intervals can represent time windows for data transmission. Merging overlapping intervals ensures efficient bandwidth utilization.
For example, merging overlapping time slots in network scheduling can help in optimizing bandwidth usage.

Solution for different languages:

Python - Merge Intervals

Code:

def merge_intervals(intervals):
    if not intervals:
        return []
    
    # Sort the intervals by their start time
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for current in intervals[1:]:
        last = merged[-1]
        # If the current interval overlaps with the last merged interval, merge them
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    
    return merged

# Test Cases
print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))  # Output: [[1, 6], [8, 10], [15, 18]]
print(merge_intervals([[1, 4], [4, 5]]))                    # Output: [[1, 5]]
print(merge_intervals([[1, 4], [0, 2], [3, 5]]))            # Output: [[0, 5]]
print(merge_intervals([]))                                  # Output: []
print(merge_intervals([[1, 4]]))                            # Output: [[1, 4]]

Output:

[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
[[0, 5]]
[]
[[1, 4]]

Explanation of the said Python code:

Function definition:

The function merge_intervals takes a list of intervals as input.

Check for empty input:

If the input list 'intervals' is empty, the function returns an empty list.

Sorting intervals:

The intervals are sorted based on their start time using a lambda function.

Initializing the Merged List:

A new list 'merged' is initialized with the first interval from the sorted list.

Iterating through intervals:

The function iterates through the remaining intervals in the sorted list.

Merging intervals:

For each interval 'current', it checks if it overlaps with the last interval in the 'merged' list ('last').
If the start time of 'current' is less than or equal to the end time of 'last', the end time of 'last' is updated to be the maximum of the end times of 'last' and 'current'.

Adding Non-Overlapping Intervals:

If 'current' does not overlap with 'last', it is added to the 'merged' list as a new interval.

Returning Results:
The 'merged' list, containing all merged intervals, is returned.

Java - Merge Intervals

Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeIntervals {
    public static int[][] mergeIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][];
        }

        // Sort the intervals by their start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1);
            int[] current = intervals[i];

            // If the current interval overlaps with the last merged interval, merge them
            if (current[0] <= last[1]) {
                last[1] = Math.max(last[1], current[1]);
            } else {
                merged.add(current);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }

    public static void main(String[] args) {
        // Test Cases
        System.out.println(Arrays.deepToString(mergeIntervals(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}})));  // Output: [[1, 6], [8, 10], [15, 18]]
        System.out.println(Arrays.deepToString(mergeIntervals(new int[][]{{1, 4}, {4, 5}})));                    // Output: [[1, 5]]
        System.out.println(Arrays.deepToString(mergeIntervals(new int[][]{{1, 4}, {0, 2}, {3, 5}})));            // Output: [[0, 5]]
        System.out.println(Arrays.deepToString(mergeIntervals(new int[][]{})));                                  // Output: []
        System.out.println(Arrays.deepToString(mergeIntervals(new int[][]{{1, 4}})));                            // Output: [[1, 4]]
    }
}

Output:

[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
[[0, 5]]
[]
[[1, 4]]

Explanation of the said Java code:

Import the necessary Java classes for using ArrayList, Arrays, and List.
mergeIntervals Method:

This method takes a 2D array int[][] intervals as input.
It first checks if the input array is empty. If so, it returns an empty 2D array.
The intervals array is sorted based on the start time of each interval using Arrays.sort.
It initializes an ArrayList 'merged' to store the merged intervals and adds the first interval from the sorted array to it.
Then, it iterates through the sorted 'intervals' array starting from index 1.
For each interval, it compares the start time of the current interval with the end time of the last merged interval.
If there's an overlap (current interval's start <= last merged interval's end), it updates the end time of the last merged interval to the maximum of both end times.
If there's no overlap, it adds the current interval to the merged list.
Finally, it converts the ArrayList to a 2D array and returns it.

Main method:
It contains test cases to demonstrate the "mergeIntervals()" method.

C++ - Merge Intervals

Code:

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

using namespace std;

vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return {};
    }

    // Sort the intervals by their start time
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);

    for (int i = 1; i < intervals.size(); ++i) {
        vector<int>& last = merged.back();
        vector<int>& current = intervals[i];

        // If the current interval overlaps with the last merged interval, merge them
        if (current[0] <= last[1]) {
            last[1] = max(last[1], current[1]);
        } else {
            merged.push_back(current);
        }
    }

    return merged;
}

int main() {
    // Test Cases
    vector<vector<int>> intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    vector<vector<int>> intervals2 = {{1, 4}, {4, 5}};
    vector<vector<int>> intervals3 = {{1, 4}, {0, 2}, {3, 5}};
    vector<vector<int>> intervals4 = {};
    vector<vector<int>> intervals5 = {{1, 4}};

    auto print = [](const vector<vector<int>>& intervals) {
        for (const auto& interval : intervals) {
            cout << "[" << interval[0] << ", " << interval[1] << "] ";
        }
        cout << endl;
    };

    print(mergeIntervals(intervals1));  // Output: [[1, 6], [8, 10], [15, 18]]
    print(mergeIntervals(intervals2));  // Output: [[1, 5]]
    print(mergeIntervals(intervals3));  // Output: [[0, 5]]
    print(mergeIntervals(intervals4));  // Output: []
    print(mergeIntervals(intervals5));  // Output: [[1, 4]]

    return 0;
}

Output:

[1, 6] [8, 10] [15, 18]
[1, 5]
[0, 5]

[1, 4]

Explanation of the said C++ code:

The "mergeIntervals()" function takes a vector of intervals as input and merges any overlapping intervals.
It first checks if the input vector 'intervals' is empty. If it is, the function returns an empty vector, indicating that there are no intervals to merge.
Otherwise, it sorts the intervals based on their start time using the "sort()" function from the <algorithm> library.
It initializes an empty vector 'merged' to store the merged intervals and adds the first interval from the sorted list to it.
Then, it iterates through the sorted intervals starting from the second interval.
For each interval, it compares it with the last interval in the 'merged' vector to determine if there's an overlap.
If there's an overlap, it merges the intervals by updating the end time of the last interval in the 'merged' vector.
If there's no overlap, it adds the current interval to the 'merged' vector.
Finally, it returns the 'merged' vector containing the merged intervals.

C# - Merge Intervals

Code:

using System;
using System.Collections.Generic;

public class MergeIntervals
{
    public static List<int[]> MergeIntervalsMethod(int[][] intervals)
    {
        if (intervals.Length == 0)
        {
            return new List<int[]>();
        }

        // Sort the intervals by their start time
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        List<int[]> merged = new List<int[]>();
        merged.Add(intervals[0]);

        for (int i = 1; i < intervals.Length; i++)
        {
            int[] last = merged[merged.Count - 1];
            int[] current = intervals[i];

            // If the current interval overlaps with the last merged interval, merge them
            if (current[0] <= last[1])
            {
                last[1] = Math.Max(last[1], current[1]);
            }
            else
            {
                merged.Add(current);
            }
        }

        return merged;
    }

    public static void Main(string[] args)
    {
        // Test Cases
        PrintIntervals(MergeIntervalsMethod(new int[][] { new int[] { 1, 3 }, new int[] { 2, 6 }, new int[] { 8, 10 }, new int[] { 15, 18 } }));  // Output: [[1, 6], [8, 10], [15, 18]]
        PrintIntervals(MergeIntervalsMethod(new int[][] { new int[] { 1, 4 }, new int[] { 4, 5 } }));  // Output: [[1, 5]]
        PrintIntervals(MergeIntervalsMethod(new int[][] { new int[] { 1, 4 }, new int[] { 0, 2 }, new int[] { 3, 5 } }));  // Output: [[0, 5]]
        PrintIntervals(MergeIntervalsMethod(new int[][] { }));  // Output: []
        PrintIntervals(MergeIntervalsMethod(new int[][] { new int[] { 1, 4 } }));  // Output: [[1, 4]]
    }

    private static void PrintIntervals(List<int[]> intervals)
    {
        foreach (var interval in intervals)
        {
            Console.Write($"[{interval[0]}, {interval[1]}] ");
        }
        Console.WriteLine();
    }
}

Output:

[1, 6] [8, 10] [15, 18]
[1, 5]
[0, 5]

[1, 4]

Explanation of the said C# code:

The "MergeIntervals" class contains a static method named "MergeIntervalsMethod()" that takes a jagged array of intervals as input and returns a list of merged intervals.
It first checks if the input array 'intervals' is empty. If it is, the method returns an empty list, indicating that there are no intervals to merge.
Otherwise, it sorts the intervals based on their start time using the "Sort()" method from the "Array" class, along with a lambda expression to compare the start times of intervals.
It initializes an empty list 'merged' to store the merged intervals and adds the first interval from the sorted array to it.
Then, it iterates through the sorted intervals starting from the second interval.
For each interval, it compares it with the last interval in the 'merged' list to determine if there's an overlap.
If there's an overlap, it merges the intervals by updating the end time of the last interval in the 'merged' list.
If there's no overlap, it adds the current interval to the 'merged' list.
The Main method demonstrates the usage of the "MergeIntervalsMethod()" with different test cases and prints the merged intervals for each case using the "PrintIntervals()" method.

JavaScript - Merge Intervals

Code:

function mergeIntervals(intervals) {
    if (intervals.length === 0) {
        return [];
    }

    // Sort the intervals by their start time
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const last = merged[merged.length - 1];
        const current = intervals[i];

        // If the current interval overlaps with the last merged interval, merge them
        if (current[0] <= last[1]) {
            last[1] = Math.max(last[1], current[1]);
        } else {
            merged.push(current);
        }
    }

    return merged;
}

// Test Cases
console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]));  // Output: [[1, 6], [8, 10], [15, 18]]
console.log(mergeIntervals([[1, 4], [4, 5]]));                    // Output: [[1, 5]]
console.log(mergeIntervals([[1, 4], [0, 2], [3, 5]]));            // Output: [[0, 5]]
console.log(mergeIntervals([]));                                  // Output: []
console.log(mergeIntervals([[1, 4]]));                            // Output: [[1, 4]]

Output:

[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
[[0, 5]]
[]
[[1, 4]]

Explanation of the said JavaScript code:

The "mergeIntervals()" function takes an array of intervals as input and returns an array of merged intervals.
It first checks if the input array 'intervals' is empty. If it is, the function returns an empty array, indicating no intervals to merge.
Otherwise, it sorts the intervals based on their start time using the "sort()" method with a custom comparison function.
It initializes an array 'merged' to store the merged intervals and adds the first interval from the sorted array to it.
Then, it iterates through the sorted intervals starting from the second interval.
For each interval, it compares it with the last interval in the 'merged' array to determine if there's an overlap.
If there's an overlap, it merges the intervals by updating the end time of the last interval in the 'merged' array.
If there's no overlap, it adds the current interval to the 'merged' array.
Finally, it returns the 'merged' array containing the merged intervals.

Time and Space Complexity:

Time Complexity:

Sorting the intervals based on their start time using intervals.sort() takes O(n log n) time, where 'n' is the number of intervals.
After sorting, iterating through the sorted intervals and merging overlapping intervals takes linear time O(n), where 'n' is the number of intervals.
Therefore, the overall time complexity is dominated by the sorting step, making it O(n log n).

Space Complexity:

The space complexity is primarily determined by the space used to store the merged intervals and any intermediate variables.
The space required to store the merged intervals is proportional to the number of intervals merged. In the worst case, if there are no overlapping intervals, the merged list would contain all intervals, resulting in O(n) space complexity.
Additionally, any intermediate variables like current and last occupy constant space.
Therefore, the overall space complexity is O(n) due to the merged list.