Merge Intervals in Java Algorithms (LeetCode)

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:

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:

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]

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.

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.

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.

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

The solution to the task looks like this:

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.

Also published here.