Palantir onsite被虐记

shawlin 发表于 2015-3-24 22:39
没理解啊，能不能细说下？

比如我有两个区间：[1,3]和[2,4]。对于区间的开始（1和3），我们给他们一个+1的tag，对于区间的结束（2和4），我们给他们一个-1的tag。这样一共得到了4个pair：(1,+1), (2, -1), (3, +1), (4, -1)。

然后，对所有pair按照坐标排序，这一步是O(nlogn)。维护一个counter表示当前点在多少个区间内部。顺序扫描所有的pair，如果遇到+1就把counter+1，遇到-1就把counter-1。counter最大的那个点就是我们要求的。

也可以用线段树，但是那样就麻烦了。

GTmac 发表于 2015-3-26 00:28
比如我有两个区间：[1,3]和[2,4]。对于区间的开始（1和3），我们给他们一个+1的tag，对于区间的结束（2和 ...

对的，没错。刚才睡觉的时候突然想到了。

之前因为考虑到反正都是nlogn的复杂度，就套个线段树好了。

但是这里因为是离线的操作，只需要查一次，所以直接统计count就可以了。

可以证明这个方法是对的。

GTmac 发表于 2015-3-26 00:28
比如我有两个区间：[1,3]和[2,4]。对于区间的开始（1和3），我们给他们一个+1的tag，对于区间的结束（2和 ...

你们是做wi输入法的那个实验室么……

我同学也是你们那出来的哈。

果然都是牛人。

shawlin 发表于 2015-3-25 23:52
建一个interval search tree? 再次感谢，求个代码链接
我的思路是 每一个interval 对应一个字符 比如
[ ...

这个好像面筋看到过，当时没想到- -||

robinho364 发表于 2015-3-25 13:25
你们是做wi输入法的那个实验室么……

我同学也是你们那出来的哈。

不是，我是IR实验室的~ 不过好多同学是WI输入法那个实验室的^^ 你的同学叫啥啊？没准我认识哈哈

GTmac 发表于 2015-3-25 11:28
比如我有两个区间：[1,3]和[2,4]。对于区间的开始（1和3），我们给他们一个+1的tag，对于区间的结束（2和 ...

我太菜了，还是没明白 对于区间
[1, 3] [2, 4]
4个pair是
(1, +1)
(2, +1)
(3, -1)
(4, -1)?
排好序后怎么找到答案呢？谢谢哈

robinho364 发表于 2015-3-25 12:23
对的，没错。刚才睡觉的时候突然想到了。

之前因为考虑到反正都是nlogn的复杂度，就套个线段树好了。
...

我太菜啊，还是没明白，求讲一下，谢谢啦！

shawlin 发表于 2015-3-27 02:47
我太菜啊，还是没明白，求讲一下，谢谢啦！

hi！

其实可以先不用考虑排序的问题。

先把线段的端点都标记了，如图所示，然后从左到右计算counter的和。

排序是为了离散化用的，只有排序以后才能达到统计过程为O(n)。

GTmac 发表于 2015-3-26 00:28
比如我有两个区间：[1,3]和[2,4]。对于区间的开始（1和3），我们给他们一个+1的tag，对于区间的结束（2和 ...

orz GTmac大神, 解法太酷炫

robinho364 发表于 2015-3-27 09:33
hi！

其实可以先不用考虑排序的问题。

Hi, 还是没明白你这个解法， 你这个算完3这个点的counter是3， 4这个点的counter是1，但是从图中看3，4不应该都是有3个overlap吗？