题目.png

题意：给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

解题思路

解法1：
1.首先分析题意，我们知道两个区间相交，有三种情况，如图：

三种情况.png

2.由题意分析可知，区间A和区间B所在的数组，是排序数组，接下来我们利用这一信息分别分析这三种情况
1）第一种情况，我们把相交区域，放入结果数组，区间A的左端此时就没有用了，所以区间A所在的数组应该移到的下一个区间，区间B的左端已经进入结果数组，所以区间B的区间应该更新start位置startb=enda
2）第二种情况，我们把相交区域，放入结果数组，区间B此时已全部放入结果数组，所以区间B所在的数组应该移动到下一个区间；区间A的左端应该舍弃，所以区间A更新start位置starta=endb
3）第三种情况，此时没有相交区域，区间A可以整个舍弃，区间A所在的数组应该移动到下一个区间；区间B不动
分析情况如图：

image.png

解题遇到的问题

无

后续需要总结学习的知识点

需要深入总结学习二叉搜索树的数据结构的特点、应用、搜索、插入、删除

##解法1
import java.util.ArrayList;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int starta = 0, enda = 0, startb = 0, endb = 0;
        int i = 0, j = 0;
        ArrayList<Integer> start = new ArrayList<Integer>();
        ArrayList<Integer> end = new ArrayList<Integer>();

        while (i < firstList.length && j < secondList.length) {
            starta = firstList[i][0];
            enda = firstList[i][1];
            startb = secondList[j][0];
            endb = secondList[j][1];
            if (starta < startb) {
                if (enda < startb) {
                    i++;
                } else {
                    if (endb < enda) {
                        start.add(startb);
                        end.add(endb);
                        firstList[i][0] = endb;
                        j++;
                    } else {
                        start.add(startb);
                        end.add(enda);
                        secondList[j][0] = enda;
                        i++;
                    }
                }
            } else {
                if (endb < starta) {
                    j++;
                } else {
                    if (enda < endb) {
                        start.add(starta);
                        end.add(enda);
                        secondList[j][0] = enda;
                        i++;
                    } else {
                        start.add(starta);
                        end.add(endb);
                        firstList[i][0] = endb;
                        j++;
                    }
                }
            }
        }

        int[][] ans = new int[start.size()][2];
        for (int k = 0; k < ans.length; k++) {
            ans[k][0] = start.get(k);
            ans[k][1] = end.get(k);
        }
        return ans;
    }
}