低调牛逼的quant公司的interval一个变种，求解

Job Hunting Interview
, , , ,
1

Given two lists of intervals, return a list of differences in sorted order
Example:
r1 = {[1,3], [5,7]}
r2 = {[2,10], [12,14]}
diff = {[1,2], [3,5], [7,10], [12,14]

2

什么公司？

3

学过interval解题的基本套路就知道，count为1的interval就是
贴下伪代码

		int[] begs =  ...;
		int[] ends = ...;
		System.out.println(Arrays.toString(begs));
		System.out.println(Arrays.toString(ends));

		int count = 0, start = 0;
		for (int i = 0, j = 0; i < begs.length;) {
			if (begs[i] < ends[j]) {
				if (++count == 1) {

				}
				i++;
			} else if (begs[i] > ends[j]) {
				if (--count == 1) {

				}
				j++;
			} else {
				// begs[i] == ends[j]
				i++;
				j++;
			}
		}
4

可以更详细点不，r1, r2的长度不一定相等

5

image
image1606×450 146 KB

最下面那行数字表示 count

6

多谢，看图有点像扫描线。不过code里的begs ends是把两个输入数组的开始、结束坐标整合起来的吗