986. Interval List Intersections

 一刷 06/2022

Version #1 Two Pointers - Not optimal

看了答案的解法写的更加简洁

先po一下自己独立写的解法

Time O(M + N)

Space O(1)

Runtime: 5 ms, faster than 53.62% of Java online submissions for Interval List Intersections.

Memory Usage: 54.9 MB, less than 27.57% of Java online submissions for Interval List Intersections.

class Solution {

    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {

        int firstPointer = 0, secondPointer = 0;

        List<int[]> overlaps = new ArrayList<>();

        while (firstPointer < firstList.length && secondPointer < secondList.length) {

            int[] first = firstList[firstPointer];

            int[] second = secondList[secondPointer];

            // [f]           [f]

            //     [s]    [s]

            if (first[1] < second[0]) {

                firstPointer++;

                continue;

            } 

            if (first[0] > second[1]) {

                secondPointer++;

                continue;

            }

            int[] overlap = new int[]{Math.max(first[0], second[0]), Math.min(first[1], second[1])};

            overlaps.add(overlap);

            if (overlap[1] == second[1]) {

                secondPointer++;

            } else {

                firstPointer++;

            }

            // [f        ]           [f]

            //   [s]    [s]

        }

        return overlaps.toArray(new int[0][]);

    }

}

Version #2 Simplified Two Pointers

Time O(M + N)

Space O(1)

Runtime: 4 ms, faster than 74.00% of Java online submissions for Interval List Intersections.

Memory Usage: 54.7 MB, less than 53.37% of Java online submissions for Interval List Intersections.

class Solution {

    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {

        int firstPointer = 0, secondPointer = 0;

        List<int[]> overlaps = new ArrayList<>();

        while (firstPointer < firstList.length && secondPointer < secondList.length) {

            int[] first = firstList[firstPointer];

            int[] second = secondList[secondPointer];

            // [f]

            //        [s]

            int lo = Math.max(first[0], second[0]);

            int hi = Math.min(first[1], second[1]);

            if (lo <= hi) {

                overlaps.add(new int[]{lo, hi});

            }

            if (first[1] < second[1]) {

                firstPointer++;

            } else {

                secondPointer++;

            }

        }

        return overlaps.toArray(new int[0][]);

    }

}