Task description: Given an array of where , merge all overlapping intervals, and return . intervals intervals[i] = [start_i, end_i] 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. Once we draw lines we can easily say which ones intersect. 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.

Meet Noonies 2022 Winner Ruslan Rakhmedov of HackerNoon Contributor of the Year- CODING

Clone Graph Blind75 LeetCode Problem

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

Make resilience your competitive advantage

Merge Intervals in Java Algorithms (LeetCode)

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Clone Graph Blind75 LeetCode Problem

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Clone Graph Blind75 LeetCode Problem

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps