题目

https://leetcode.com/problems/interval-list-intersections/

题解

本题用双指针。（想了下，也可以用线段树，和天际线那道题类似）

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int i = 0;
        int j = 0;
        List<int[]> list = new ArrayList<>();
        while (i < firstList.length || j < secondList.length) {
            if (i == firstList.length) {
                j++;
            } else if (j == secondList.length) {
                i++;
            } else {
                // 有重叠情况：
                // [    ]
                //    [    ]

                //  [   ]
                // [       ]

                //    [    ]
                // [    ]

                // [       ]
                //  [   ]

                // 无重叠情况：
                // [    ]
                //        [    ]

                //        [    ]
                // [    ]
                int start = Math.max(firstList[i][0], secondList[j][0]);
                int end = Math.min(firstList[i][1], secondList[j][1]);
                if (start <= end) {
                    list.add(new int[]{start, end});
                    if (firstList[i][1] < secondList[j][1]) {
                        i++;
                    } else {
                        j++;
                    }
                } else {
                    if (firstList[i][1] < secondList[j][0]) {
                        i++;
                    } else {
                        j++;
                    }
                }
            }
        }
        int[][] result = new int[list.size()][];
        for (int k = 0; k < list.size(); k++) {
            result[k] = list.get(k);
        }
        return result;
    }
}