大厂面试真题详解:合并区间

给出若干闭合区间,合并所有重叠的部分。
在线评测地址:领扣题库官网

样例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,22,46,10。

可以看出,当我遍历数组的时候,每次访问一个区间ai,都能保证:如果ai和它前面的区间不相交,那么ai后面的任意区间都不能和ai前面的任意区间相交。这样就保证了时间复杂度为O(n)级别,即不会出现其他的遍历。

比如区间[5,7],他和前面的区间都没有相交,他后面的所有区间和它一样,没有和[5,7]前面的区间有交集。

代码思路

  1. 对区间数组按区间的左端点start排序。
  2. 将最后的区间赋值lastinterval为intervals[0]。
  3. 遍历输入,如果lastinterval和当前区间相交,合并两个区间。
  4. 如果不相交,将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);
    }
}

更多题解参考:九章官网Solution

上一篇:大厂面试真题详解:带最小值操作的栈


下一篇:大厂面试真题题解:目标最后位置