No.0015-CareerCup

Implement method:
List<Range> getRanges(List<Shard> shards, List<Key> keys)
That returns list of ranges. Each range represents multiple keys aggregated over a shard:
n-keys -> 1-shard -> 1-range
Method should return no more than 1 range per shard that spans all keys or their parts belonging to this shard.
Each of the 'Range', 'Shard' and 'Key' classes have 'end' and 'start' fields of int type, where 'start' is inclusive and 'end' is exclusive.
Example:
1-9,12-59,100-999 <- shards (input)
2-3,6-8,11-20,200-220 <- keys (input)
2-8,12-20,200-220 <- ranges (output)
太长懒得翻译

1. 询问

给出的input是不是已经排好序的？假设shards和keys已经排好序，而且是升序。
input是不是都是非重合的？假设shards和keys都是非重合的。

2. 分析

题目分析

这道题是属于区间操作类的题。input有两种，shards和keys，要做的就是把keys在shards里面的范围合并到一起，取其首尾。当然keys可能会超出一些范围，都需要处理。
这道题的区间操作不是常见的merge，但其实也不复杂，关键是处理一些corner case，比如跨多个shards的key怎么处理，细节实现比较重要。
具体算法实现，可以采用双指针，假设是p指向shards的list，q指向keys的list。注意结果的数目是和shards相对应的，如果不考虑空range的情况，也就是说一开始可以根据shards的个数来进行range的初始化，然后在后面对这些range进行赋值，最后把空的range丢掉。这样可以大大简化整个流程。
那么p和q指向的区间对比，无非两种大的情况，相交或者不相交。这里的思考很关键，因为要好好考虑哪些条件决定下一步移动哪个指针。假设p指向的shard是[a,b)，q指向的key是[c,d)。
那么以shard为基准，key无非几种情况：

• 相交
  相交又有三种情况，一种是shard完全包括key，一种是key在shard左边，另外一种是key在shard右边。对于第一种情况和第二种情况，shard还没有被探索完毕，也就说有可能还有key会和shard相交，因此q应该加1，指向下一个key；而对于第三种情况，shard已经完了，因为序列的递增，下一个key不可能再和这个shard有交集，反而是有可能当前的key与下一个shard有交集。因此这时候p加1.
• 不相交
  不相交只有两种情况，key在shard左边或者右边，在左边当然是q+1，在右边p+1.

考虑边界情况，因为题目规定区间包含开始而不包含结束，因此可以写出以下判断条件：

• 相交且key在shard左边：d>a and c<=a; q++
• 相交且shard完全包括key：c>=a and d<=b; q++
• 相交且key在shard右边：c<b and d>b; p++
• 不相交且key在shard左边：d<=a; q++
• 不相交且key在shard右边：c>=b。p++

如何合并区间？因为已经把shard和range一一对应，于是只需要把当前的range和key合并即可。初次合并，range并没有值，赋值为key和shard的交集；之后，取range的左端加上新的key的右端为新的range，当然要注意不能超出shard的范围。
为方便起见，代码里的shard，key，range都用interval来表示。
时间复杂度O(m+n)，空间复杂度O(n)，n是shard的个数，m是key的个数。

3. 代码

class Interval:
    def __init__(self, start, end):
        self.start, self.end = start, end

class Solution(object):
    def sol(self, shards, keys):
        if not shards or not keys:
            return []
        i, j, ret = 0, 0, [None] * len(shards)
        while i < len(shards) and j < len(keys):
            sh = shards[i]
            a, b = sh.start, sh.end
            while j < len(keys):
                k = keys[j]
                c, d = k.start, k.end
                if not (d<=a or c>=b): # if intersect
                    if not ret[i]:   # if range not initialized, do it
                        ret[i] = Interval(max(a, c), min(b, d))
                    else:   # else put them together
                        ret[i].start = max(min(ret[i].start, c), a)
                        ret[i].end = min(max(ret[i].end, d), b)
                    if d > b:   # if key is on the right, look at next shard
                        i += 1
                        break
                    else:
                        j += 1
                else:
                    if d <= a:
                        j += 1
                    else:
                        i += 1
                        break
        return [x for x in ret if x]

4. 总结

细节实现题，难度medium。