Google 面试题：合并区间

zzzrf：给出若干闭合区间，合并所有重叠的部分。

点此在线做题

样例 1:

输入: [(1,3)]
输出: [(1,3)]

样例 2:

输入:  [(1,3),(2,6),(8,10),(15,18)]
输出: [(1,6),(8,10),(15,18)]

解题思路

对应两个区间 a, b，如何判断它们相交？
当 a, b 满足 max(a.start,b.start)<=min(a.end,b.end)max(a.start,b.start)<=min(a.end,b.end)时，两者相交。
我们应考虑某种排序方式，使得所有相交的区间对应一段连续的数组下标，这样方便我们进行之后的合并操作。
这种排序方式应该是对区间的左端点按从小到大的方式进行排序，假设我们存在一个已经按照上面方式排序的数组：[1，2][1，3][2，4][5，7][6，10][6，11]。
可以看出，当我遍历数组的时候，每次访问一个区间 ai，都能保证：如果 ai 和它前面的区间不相交，那么 ai 后面的任意区间都不能和 ai 前面的任意区间相交。这样就保证了时间复杂度为 O(n)级别，即不会出现其他的遍历。
比如区间[5，7]，他和前面的区间都没有相交，他后面的所有区间和它一样，没有和[5，7]前面的区间有交集。

代码思路

对区间数组按区间的左端点 start 排序。
将最后的区间赋值 lastinterval 为 intervals[0]。
遍历输入，如果 lastinterval 和当前区间相交，合并两个区间。
如果不相交，将 lastinterval 加入结果，并将 lastinterval 赋值为当前的区间。

复杂度分析

设区间的个数为 N 。
时间复杂度

排序的时间复杂度为 O(NlogN)。
遍历一遍数组的时间复杂度为 O(N)。
总时间复杂度为 O(NlogN)。
空间复杂度
空间复杂度为 O(n)，可能存在每一个区间都不与任何一段区间相交，返回的答案和传入的参数长度相等。

public class Solution {
    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() == 0) {
            return intervals;
        }
        
        // 根据区间的 start 值排序
        intervals.sort(Comparator.comparing(i -> i.start));
        
        List<Interval> result = new ArrayList<Interval>();
        Interval lastInterval = intervals.get(0);
        
        // 如果两段区间有交集的话，合并两段区间
        // 没有的话，将最后的区间加入答案，并令新的区间作为最后的区间
        for (Interval interval: intervals) {
            if (haveIntercation(lastInterval, interval)) {
                lastInterval = mergeTwoIntervals(lastInterval, interval);
            }
            else {
                result.add(lastInterval);
                lastInterval = interval;
            }
        }
        result.add(lastInterval);
        
        return result;
    }
    // 合并两段区间
    private Interval mergeTwoIntervals(Interval a, Interval b) {
        return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
    }
    // 判断区间是否有交集，要满足较大的 start 小于等于较小的 end
    private boolean haveIntercation(Interval a, Interval b) {
        return Math.max(a.start, b.start) <= Math.min(a.end, b.end);
    }
}

Google 验证器出现的数字是预先有的？

CSGO：我发现我经常登录一些账号，好像经常就那么几组数字，都能背了，这是巧合还是记忆错乱？或则它是有多少组固定的数字？那么类似 Steam 的手机令牌中也是一样的原理吗？lycc：https://zh.m.wikipedia.org/zh-cn/Google%E8%BA%AB%E4%BB%BD%E9%AA%8C%E8%AF%81%E5%99%A8了解一…

Google 的磁悬浮负载均衡器

holinhot：https://research.google/pubs/pub44824/ 想试一试这个磁悬浮负载均衡器，文档我看了，说得很牛逼的样子，但是我找了很久没找到在哪下载啊。难道不是开源的，只是出来水一下让大家看吗？holinhot：https://opensource.google/projects/list/featured 在这也没找…

Google Play 购买游戏安装后卸载会触发自动退款？

Gitch：一脸懵 b，20 点 39 分购买了个游戏，然后安装下来，玩到 51 分左右，删了，然后 Google play 突然同时给我发了邮件说已同意您的退款申请？？（我并没有申请这么人性化的吗？想了解具体规则......多少时间内主动卸载游戏会触发这种自动退款效果？游戏是几何冲刺，1.99 刀。

一个 Google Drive 搜索引擎

xinyana：https://zhao.pp.ua 一个基于ElasticSearch的 Google Drive 搜索引擎,可搜索、可直接下载

国内几个主流输入法还能在 Google Play 上搜索到吗？

ReZer0：印象中去年还是更早时候，在 Google Play 上还能看到类似 QQ 拼音，讯飞语音之类的输入法，最近在找的时候发现都找不到了。网页版和心愿单中可以看到，但均提示不兼容设备无法安装。软件更新信息还是比较新的，评论也比较靠前。这种情况是被下架了吗？还是地区限制了？bunnyblueair：地区限制吧