题解

题目描述

Insert Interval

即向有序、不重叠的区间序列中插入一个区间。如区间产生重叠，则合并。求插入新区间后的区间序列。

如：A = [1,3],[6,9]，插入[2,6]，插入后新序列为[1,9]。

题解

由于序列有序，利用二分查找可在O(log N)时间内找到待插入区间的位置区间，而后合并区间即删除插入后产生的的重叠区间，由于是在数组上进行删除操作，时间复杂度为O(N)。即总体时间复杂度为O(N)，空间复杂度为O(1)。

代码

typedef std::vector
    
      ParamType;bool cmpStart(const Interval& a, const Interval& b) {    return a.start > b.start;}bool cmpEnd(const Interval& a, const Interval& b) {    return a.end < b.end;}class Solution {public:    vector
     
      & insert(vector
      
       & intervals, Interval newInterval) {        ParamType::reverse_iterator start(std::lower_bound(intervals.rbegin(), intervals.rend(), newInterval, cmpStart));        ParamType::iterator end(std::upper_bound(intervals.begin(), intervals.end(), newInterval, cmpEnd));        if (start != intervals.rend() && newInterval.start <= start->end) {            if (end != intervals.end() && newInterval.end >= end->start) {                start->end = end->end;                intervals.erase(intervals.begin() + (intervals.size() - (start - intervals.rbegin())), end + 1);            } else {                start->end = newInterval.end;                intervals.erase(intervals.begin() + (intervals.size() - (start - intervals.rbegin())), end);            }        } else {            if (end != intervals.end() && newInterval.end >= end->start) {                end->start = newInterval.start;                intervals.erase(intervals.begin() + (intervals.size() - (start - intervals.rbegin())), end);            } else {                ParamType::iterator in = intervals.begin() + (intervals.size() - (start - intervals.rbegin()));                if (in != end) {                    *in = newInterval;                    intervals.erase(in + 1, end);                } else {                    intervals.insert(in, newInterval);                }            }        }        return intervals;    }};

总结

主要应用了二分查找的思想。

转载地址：http://nvnlx.baihongyu.com/

你可能感兴趣的文章