• 解题:给定区间集合插入新区间 [难度难]

    2015/09/28 JSRGFJZ 7 评论

题目:

有一组非重叠区间,插入一组新区间。(可以合并)

示例:

[1,3],[6,9], 插入 [2,5] ,结果为 [1,5],[6,9].
[1,2],[3,5],[6,7],[8,10],[12,16], 插入[4,9],结果为 [1,2],[3,10],[12,16].

思路:

首先考虑两级情况,要么在最左边,要么在最右边。这种情况最简单,直接插入。

接下来就是难点,注意情况newInterval.start > intervals[i].end,是在区间进行比较。

相反newInterval.end < intervals[j].start,这是在区间左边进行比较。

也就是这个时候得出i和j,分别从左边右边得出结论。

这个时候继续判断i和j,只有两种情况。j<i以及j>=i。这个时候还得小心,究竟新区间与原来区间有没有重叠,这也是j<i的情况,剩下的很简单。

代码:

 

2 收藏


直接登录
最新评论
  • exlsunshine 学生 2015/10/01

    线段树?

    • JSRGFJZ 学生 2015/10/01

      class Solution {
      public:
      vector insert(vector &intervals, Interval newInterval) {
      vector result;

      const int n = intervals.size();
      if (n == 0) {
      result.push_back(newInterval);
      return result;
      }
      if (newInterval.start > intervals[n-1].end) {
      result = intervals;
      result.push_back(newInterval);
      return result;
      }
      if (newInterval.end intervals[i].end) {
      result.push_back(intervals[i++]);
      }

      int j = n – 1;
      while (newInterval.end < intervals[j].start) {
      j–;
      }

      if (j < i) {
      result.push_back(newInterval);
      }
      else {
      newInterval.start = min(newInterval.start, intervals[i].start);
      newInterval.end = max(newInterval.end, intervals[j].end);
      result.push_back(newInterval);
      }

      result.insert(result.end(), intervals.begin()+j+1, intervals.end());

      return result;
      }
      };

  • 难度提升一下,如果原来的interval没有排序呢?
    boolean ifOverlap(Interval i1, Interval i2) {
    if (i1.start > i2.end || i1.end < i2.start) {
    return false;
    }
    return true;
    }

    ArrayList insert(ArrayList intervals, Interval newInterval) {
    checkNotNull(intervals);
    checkNotNull(newInterval);
    checkLegaInterval(newInterval);
    ArrayList result = new ArrayList();
    for(Interval interval : intervals) {
    if (ifOverlap(interval, newInterval)) {
    newInterval.start = Math.min(interval.start, newInterval.start);
    newInterval.end = Math.max(interval.end, newInterval.end);
    } else {
    result.push(interval);
    }
    }
    result.push(newInterval);
    }

  • ppyyf 运维工程师 2015/10/04

    复杂度O(n),n为原有区间个数。该算法不要求原有区间是否已排序。

    步骤0:原有区间为集合A:{i1,i2,i3…,iN},新加入区间为集合B:{i’},其中B始终有且只有一个元素。
    步骤1:X=1
    步骤2:从集合A中取区间iX,与B中唯一元素区间i’比较,若iX与i’不相交,将iX放回集合A且B中i’保持不变;若iX与i’相交,则iX不再放回A,并用iX与i’的交集替代B中唯一元素。
    步骤3:X=X+1,若X>A的元素个数N,跳至步骤4,否则跳至步骤2。
    步骤4:将B中唯一元素区间放入A中相应位置。