Interval Overlaps

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,000 where n is the length of l0
• m ≤ 100,000 where m is the length of l1

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)