## Task description:

Given an array of `intervals` where `intervals[i] = [start_i, end_i]`, merge all overlapping intervals, and return *an array of the non-overlapping intervals that span every input interval*.

\
**Example 1:**

```javascript
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, merge them into [1,6].
```

\
**Example 2:**

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

\
**Constraints:**

* `1 <= intervals.length <= 10^4`
* `intervals[i].length == 2`
* `0 <= starti <= endi <= 10^4`

## Reasoning:

Let’s try to do something natural. Let’s draw intervals from the first example. It’ll help us to understand the nature of the problem and decide what approach to take in order to solve this problem.

\
We have these intervals \[1,3\],\[2,6\],\[8,10\],\[15,18\]

 ![Intervals](https://cdn.hackernoon.com/images/-c7a3pwk.png)

\
Looking at this chart we can make 2 essential observations.


1. Once we draw lines we can easily say which ones intersect.
2. Once we draw lines they become sorted.

Having this in mind we can continue with the solution. 

## Solution:

The first thing we want to do is to sort all the intervals we have. We do this to merge them together when we look at the chart above. It’s simple sorting, we start at the point of an interval and then by the end.

\
```java
Arrays.sort(intervals, (a, b) ->
{
   if (a[1] == b[1])
   {
      return a[0] - b[0];
   }

   return a[1] - b[1];
});
```

\
Once intervals are sorted, we can start merging them. Looking at the chart above, we can make an important observation — intersecting intervals overlap or they start at the end position of another interval. We’ll use LinkedList as it provides the method getLast(). We can also use ArrayList and get last element by calling list.get(list.size() — 1). For each interval, we check if we have an intersection with the previous one. If we do have an intersection, we simply merge them together and put them back into the list.

\
```java
LinkedList<int[]> list = new LinkedList<>();
for (int[] interval : intervals)
{
   if (!list.isEmpty() && list.getLast()[1] >= interval[0])
   {

      while (!list.isEmpty() && list.getLast()[1] >= interval[0])
      {
         interval[0] = Math.min(list.getLast()[0], interval[0]);
         interval[1] = Math.max(list.getLast()[1], interval[1]);
         list.removeLast();
      }
   }

   list.addLast(interval);
}
```

\
The last thing to do is to create the answer. We do it because we don’t know in the beginning how many elements don’t intersect with each other.

\
```java
int pos = 0;
int[][] answer = new int[list.size()][];
for (int[] inteval : list)
{
   answer[pos++] = inteval;
}
```

\
The solution to the task looks like this:

\
```java
public int[][] merge(int[][] intervals)
{
   Arrays.sort(intervals, (a, b) ->
   {
      if (a[1] == b[1])
      {
         return a[0] - b[0];
      }

      return a[1] - b[1];
   });

   LinkedList<int[]> list = new LinkedList<>();
   for (int[] interval : intervals)
   {
      if (!list.isEmpty() && list.getLast()[1] >= interval[0])
      {

         while (!list.isEmpty() && list.getLast()[1] >= interval[0])
         {
            interval[0] = Math.min(list.getLast()[0], interval[0]);
            interval[1] = Math.max(list.getLast()[1], interval[1]);
            list.removeLast();
         }
      }

      list.addLast(interval);
   }

   int pos = 0;
   int[][] answer = new int[list.size()][];
   for (int[] inteval : list)
   {
      answer[pos++] = inteval;
   }

   return answer;
}
```

\
The code above gives looks good. It has n log n time and linear space complexity.

\
 ![](https://cdn.hackernoon.com/images/-jnb3p59.png)


---

Also published [here.](https://levelup.gitconnected.com/java-algorithms-merge-intervals-leetcode-24a3277cfa28)

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

Merge Intervals in Java Algorithms (LeetCode)

Too Long; Didn't Read

@rakhmedovrs

RELATED STORIES