Merge Intervals

This is a classic interview question that is used in a lot in technical interviews, frequently in the form of a calendar or meeting management application. As such, we'll also assume the same use case, as it's easier to visualize.

Suppose we're given a few arrays, like [1, 4], [2, 5], [7, 10], [12, 16], representing time intervals. The elements within the arrays represent a start time and end time of a meeting. So an array "time range" of [1, 4] would mean that the event starts at 1-o'clock and ends at 4-o'clock.

Now, what if we wanted to merge any overlapping meetings? If one meeting runs into the time of another, we'll want to combine them into one. As such, [1, 4] and [2, 5], who overlap between 4 o'clock and 5 o'clock, would be combined into [1, 5].

For the above example of [1, 4], [2, 5], [7, 10], [12, 16], we would want to return [1, 5], [7, 10], [12, 16]. Can you write a method that will do this?

Constraints

• Size of array ranges <= 100000
• The array will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(n)

```js
function mergeIntervals(ranges) {
	// return ranges
	return result;
}
```
```java
public ArrayList<Interval> mergeIntervals(ArrayList<Interval> ranges) {
    // return ranges
    return result;
}
```
```javascript
function mergeIntervals(ranges) {
    // return ranges
    return result;
}
```
```python
def merge_intervals(ranges):
    # return ranges
    return result
```
```cpp
std::vector<Interval> mergeIntervals(std::vector<Interval> &ranges) {
    // return ranges
    return result;
}
```
```csharp
public static List<Interval> MergeIntervals(List<Interval> ranges) {
    // return ranges
    return result;
}
```
```go
func mergeIntervals(ranges []interval) []interval {
   // return ranges
   return result
}
```

Demystifying the Merge: A Deep Dive into Merging Time Ranges

The Initial Hurdle: Perceived Complexity

The process of merging time ranges can appear daunting at first, mostly due to misconceptions about how the merging unfolds. Yet, in reality, there's a clear workflow to follow. To build intuition, it's helpful to start with the most simplified example and dissect it step by step.

Setting the Stage: A Simple Example

Imagine we are given just two time ranges to merge: [1, 4] and [2, 5]. It's evident that these ranges overlap, but how exactly should we merge them?

Finding the Start Time

We observe that 1 precedes 2. So, the merged range must start at the earliest time, which in this case is 1. It's like having two runners on a track; naturally, the one who starts first sets the pace. This choice is relatively straightforward if you sort the intervals by their start times.

Deciding the End Time

Deciding the end time is a bit more nuanced. While 4 comes before 5, we want our merged range to encapsulate all overlapping time. So, the end time must be 5. Think of this as ensuring the last runner crosses the finish line.

The Backbone: Sorting as a First Step

Sorting the ranges helps us establish a chronological order, making it easier to merge them. The lowest starting time will always be the beginning of our merged range, and from there, we can focus on the end times. Here's how to sort these ranges in both JavaScript and Python:

const ranges = [[1, 4], [2, 5]];

ranges.sort(function(a, b) {
  return a[0] - b[0] || a[1] - b[1];
});

from functools import cmp_to_key

ranges = [[2, 5], [1, 4]]

def compare(a, b):
    return a[0] - b[0] or a[1] - b[1]

ranges.sort(key=cmp_to_key(compare))
print(ranges)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<int[]> ranges = new ArrayList<>();
        ranges.add(new int[]{1,4});
        ranges.add(new int[]{2,5});

        Collections.sort(ranges, (a, b) -> {
            return a[0] - b[0] != 0 ? a[0] - b[0] : a[1] - b[1];
        });
    }
}

#include <algorithm>
#include <vector>

int main() {
    std::vector<std::pair<int, int>> ranges = {{1, 4}, {2, 5}};

    std::sort(ranges.begin(), ranges.end(),
              [](std::pair<int, int> a, std::pair<int, int> b) {
                  return a.first != b.first ? a.first - b.first : a.second - b.second;
              });
    return 0;
}

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var ranges = new List<Tuple<int, int>>
        {
            Tuple.Create(1,4),
            Tuple.Create(2,5)
        };

        ranges.Sort((a, b) => a.Item1 != b.Item1 ? a.Item1 - b.Item1 : a.Item2 - b.Item2);
    }
}

package main

import (
    "sort"
)

type Range struct {
    first int
    second int
}

func main() {
    ranges := []Range{
        {first: 1, second: 4},
        {first: 2, second: 5},
    }

    sort.SliceStable(ranges, func(i, j int) bool {
        if ranges[i].first == ranges[j].first {
            return ranges[i].second < ranges[j].second
        }
        return ranges[i].first < ranges[j].first
    })
}

A Roadmap for Merging Time Ranges

Merging time ranges is a task that becomes much more manageable once you understand the underlying structure:

1. Sort the Ranges: Establish a chronological order.
2. Determine the Start Time: Choose the earliest start time among overlapping intervals.
3. Decide the End Time: Make sure to cover all time within the overlapping intervals.

By following this methodical approach, you'll find that what seemed like a challenging problem is, in fact, quite solvable.

The Anatomy of Merging: Scenarios, Steps, and Solution Complexity

A Closer Look at Merge Scenarios

Before diving further into the code, let's acquaint ourselves with the various situations where merging becomes necessary. For a detailed understanding, you can explore all possible merging scenarios here.

Initialize Result Storage

Once our ranges are sorted, we start with an empty result array to store our final merged intervals.

Iterating and Merging: A Walkthrough

After sorting by the starting time, we have our array looking like [[1, 4], [2, 5], [7, 10], [12, 16]]. Now comes the fun part — iterating through these intervals and deciding when to merge.

Determining Overlap via Code

We'll iterate through our sorted ranges. To do this efficiently, we maintain a variable called last, which tracks the last interval we've encountered. As we go through each range r in ranges, we'll need to decide whether to extend last or append a new range to our result. Here's how:

1. Checking for Overlap: If the start time of r (r[0]) is less than or equal to the end time of last (last[1]), we have an overlap.
2. Extending the Interval: In the case of an overlap, we update last[1] to be the maximum between r[1] and last[1]. This ensures that last covers the entirety of the overlapping period.

Identifying Clear Separations

If there is no overlap — i.e., a "clear separation" exists — we simply append the new range to our result. A clear separation is evident when last[1] is less than r[0]. In such a case, r starts strictly after last ends, and hence no merge is necessary.

```js
const ranges = [
  [1, 4],
  [2, 5],
];

const result = [];
let last;
ranges.forEach(function (r) {
  // compare this new range to the last one we tracked
  // if this range has a time gap before the next event, add to results
  if (!last || r[0] > last[1]) {
    last = r;
    result.push(last);
  } else if (r[1] > last[1]) {
    // otherwise if its end time is longer than the last,
    // extend the last range's end time to encompass this interval too
    last[1] = r[1];
  }
});

console.log(result);
```
```py
from functools import cmp_to_key

ranges = [[2, 5], [1, 4]]

def compare(a, b):
    return a[0] - b[0] or a[1] - b[1]

ranges.sort(key=cmp_to_key(compare))

result = []

last = None
for r in ranges:
  # compare this new range to the last one we tracked
  # if this range has a time gap before the next event
  # e.g. first element of r "clears" second element of last
  # add to results
  if not last or r[0] > last[1]:
    last = r
    result.append(last)
  elif r[1] > last[1]:
    # otherwise if its end time is longer than the last,
    # extend the last range's end time to encompass this interval too
    last[1] = r[1]

print(result)
```
```java
import java.util.Arrays;
import java.util.Comparator;
import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    int[][] ranges = {{2,5},{1,4}};

    // Sort ranges
    Arrays.sort(ranges, new Comparator<int[]>(){
      public int compare(int[] a, int[] b){
        return a[0] - b[0] != 0 ? a[0] - b[0] : a[1] - b[1];
      }
    });

    ArrayList<int[]> result = new ArrayList<int[]>();
    int[] last = null;
    for (int[] r : ranges) {
      // compare this new range to the last one we tracked
      // if this range has a time gap before the next event,
      // add to results
      if (last == null || r[0] > last[1]) {
        last = r;
        result.add(last);
      } else if (r[1] > last[1]) {
        // otherwise if its end time is longer than the last,
        // extend the last range's end time to encompass this interval too
        last[1] = r[1];
      }
    }

    // print results
    for(int[] range : result) {
      System.out.print(Arrays.toString(range));
    }
  }
}
```
```cpp
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
  std::vector<std::pair<int,int>> ranges = {{2,5},{1,4}};
  std::sort(ranges.begin(), ranges.end());

  std::vector<std::pair<int,int>> result;
  std::pair<int,int> last = {0,0};
  for (auto r : ranges) {
    // compare this new range to the last one we tracked
    // if this range has a time gap before the next event,
    // add to results
    if (last.second == 0 || r.first > last.second) {
      last = r;
      result.push_back(last);
    } else if (r.second > last.second) {
      // otherwise if its end time is longer than the last,
      // extend the last range's end time to encompass this interval too
      last.second = r.second;
    }
  }

  // print results
  for (auto r : result) {
    std::cout << "{" << r.first << "," << r.second << "}";
  }
  return 0;
}
```
```csharp
using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        var ranges = new Tuple<int, int>[] {
            new Tuple<int, int>(2, 5),
            new Tuple<int, int>(1, 4)
        };

        // sort ranges
        Array.Sort(ranges, (a, b) => a.Item1 != b.Item1 ? a.Item1 - b.Item1 : a.Item2 - b.Item2);

        var result = new List<Tuple<int, int>>();
        Tuple<int, int> last = null;
        foreach (var r in ranges) {
            // compare this new range to the last one we tracked
            // if this range has a time gap before the next event, add to results
            if (last == null || r.Item1 > last.Item2) {
                last = r;
                result.Add(last);
            } else if (r.Item2 > last.Item2) {
                // otherwise if its end time is longer than the last
                // extend the last range's end time to encompass this interval too
                last = new Tuple<int, int>(last.Item1, r.Item2);
            }
        }

        // print results
        result.ForEach(r => {Console.WriteLine($"({r.Item1}, {r.Item2})");});
    }
}
```
```go
package main

import (
	"fmt"
	"sort"
)

func main() {
	ranges := [][]int{{2, 5}, {1, 4}}

	// Sort ranges
	sort.Slice(ranges, func(i, j int) bool {
		return ranges[i][0] != ranges[j][0] && ranges[i][0] < ranges[j][0] || ranges[i][1] < ranges[j][1]
	})

	var result [][]int
	last := make([]int, 2)

	for _, r := range ranges {
		// compare this new range to the last one we tracked
		// if this range has a time gap before the next event, add to results
		if last[1] == 0 || r[0] > last[1] {
			last = r
			result = append(result, last)
		} else if r[1] > last[1] {
			// otherwise if its end time is longer than the last
			// extend the last range's end time to encompass this interval too
			last[1] = r[1]
		}
	}

	// print results
	for _, r := range result {
		fmt.Println(r)
	}
}
```

Complexity Breakdown

Given that the input intervals are already sorted, our solution exhibits a linear time complexity of (O(n)) and linear space complexity. This is because we iterate through each of the (n) intervals exactly once.

The Final Logic: A Code Snapshot

The final logic could be understood as below (actual code not shown here). While iterating through the sorted array: - Check for overlap with the last interval. - Extend last if there's an overlap. - Append to result in case of a clear separation.

By following this systematic approach, merging time intervals becomes a straightforward task, completely doable within reasonable time and space constraints.

Merging Intervals: A Detailed Walkthrough

Let's get our hands dirty by stepping through the actual code to merge the given list of intervals: [[1, 4], [2, 5], [7, 10], [12, 16]].

Preparing the Ground: Initial Sort and Setup

Before jumping into merging, we sort our intervals by their start times.

intervals = [[1, 4], [2, 5], [7, 10], [12, 16]]
intervals.sort(key=lambda x: x[0])

Also, initialize an empty array called result to store the merged intervals.

result = []

Step 1: Seed the result Array

We start by taking the first interval [1, 4] from our sorted array and appending it to result.

result.append(intervals[0])

At this point, result = [[1, 4]].

Step 2: Enter the Loop: First Iteration

Now, we loop through the remaining intervals in the sorted array, starting with [2, 5].

current = [2, 5]
last = result[-1]  # [1, 4]

Here, last is [1, 4], and current is [2, 5]. We notice that current[0] <= last[1], which indicates an overlap. So, we extend last to cover current.

if current[0] <= last[1]:
    last[1] = max(current[1], last[1])  # max(5, 4) = 5

After this step, result = [[1, 5]].

Step 3: Second Iteration

Next, we consider the interval [7, 10].

current = [7, 10]
last = result[-1]  # [1, 5]

Here, current[0] > last[1], meaning there's a gap. So, we simply append current to result.

result.append(current)

Now, result = [[1, 5], [7, 10]].

Step 4: Final Iterations

We repeat the above steps for [12, 16]. Since it doesn't overlap with the last interval [7, 10], we add it to the result as is.

result.append([12, 16])

Our final result array becomes [[1, 5], [7, 10], [12, 16]].

And there you have it! We've successfully merged the intervals using Python code. This step-by-step walkthrough should give you a detailed understanding of how interval merging works in practice.

One Pager Cheat Sheet

• We can write a method that merges any overlapping meetings in a given array of time intervals with a time complexity of O(n) and a space complexity of O(n).
• Merging time ranges is relatively straightforward, as long as the intervals are properly sorted; we just need to take the smallest beginning/start time, and follow the chronological order to find the largest end/finishing time.
• We iterate through the sorted array of intervals, comparing the last interval and referencing a result list to store modified intervals from clear separations or overlaps.