Description
You are given a list of closed intervals l0 and another list of intervals l1. Individually, each list is non-overlapping and are sorted in ascending order.
Return the overlap of the two intervals sorted in ascending order.
Constraints:
-
n ≤ 100,000wherenis the length ofl0 -
m ≤ 100,000wheremis the length ofl1
Example 1
Input
l0 = [
[1, 3],
[5, 6],
[7, 9]
]
l1 = [
[1, 4],
[5, 7]
]
Output
[
[1, 3],
[5, 6],
[7, 7]
]
Example 2
Input
l0 = [
[1, 3],
[5, 6],
[7, 9]
]
l1 = [
[100, 200]
]
Output
[]
Intuition
Implementation
import java.util.*;
class Solution {
public int[][] solve(int[][] l0, int[][] l1) {
ArrayList<int[]> list = new ArrayList<>();
int i0 = 0, i1 = 0, n0 = l0.length, n1 = l1.length;
while (i0 < n0 && i1 < n1) {
int low = Math.max(l0[i0][0], l1[i1][0]);
int high = Math.min(l0[i0][1], l1[i1][1]);
if (low <= high) {
list.add(new int[] {low, high});
}
if (l0[i0][1] < l1[i1][1]) {
i0++;
} else {
i1++;
}
}
int[][] ans = new int[list.size()][2];
for (int i = 0; i < ans.length; i++) {
ans[i] = list.get(i);
}
return ans;
}
}
Time Complexity
- Time: O(n+m)
- Space:O(n)
Top comments (0)