This content originally appeared on Level Up Coding - Medium and was authored by Ruslan Rakhmedov
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 cover all the intervals in the input.
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 important observations.
- Once we drew lines we can easily say which one intersect each other.
- Once we drew lines they became sorted.
Having this in mind we can proceed to the solution
Solution:
The first thing we want to do is to sort all the intervals we have so we can merge them together as we do in our mind when we look at the chart above. It’s simple sorting, we first sort by the starting point of an interval and then by end one.
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 important observation — intersecting intervals has some overlap or they start at the end position of another interval. We’ll use LinkedList as it provides 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 intersection with the previous one. If we have intesection we simply merge them together and put back into 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 each other.
int pos = 0;
int[][] answer = new int[list.size()][];
for (int[] inteval : list)
{
answer[pos++] = inteval;
}
So the solution to 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 us good results. It has n log n time and linear space complexity.
Java algorithms: Merge Intervals (LeetCode) was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Ruslan Rakhmedov
Ruslan Rakhmedov | Sciencx (2022-06-20T11:49:53+00:00) Java algorithms: Merge Intervals (LeetCode). Retrieved from https://www.scien.cx/2022/06/20/java-algorithms-merge-intervals-leetcode/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.