[LeetCode] Insert Interval 插入区间

2018-10-18  本文已影响10人  高思阳

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

这道题让我们在一系列非重叠的区间中插入一个新的区间,可能还需要和原有的区间合并,那么我们需要对给区间集一个一个的遍历比较,那么会有两种情况,重叠或是不重叠,不重叠的情况最好,直接将新区间插入到对应的位置即可,重叠的情况比较复杂,有时候会有多个重叠,我们需要更新新区间的范围以便包含所有重叠,而且最后处理的时候还需要删除原区间集中所有和新区间重叠的区间,然后插入新区间即可。具体思路如下:

NSMutableArray *arr = [NSMutableArray array];

    [arr addObject:[NSValue valueWithPoint:NSMakePoint(1, 2)]];
    [arr addObject:[NSValue valueWithPoint:NSMakePoint(3, 5)]];
    [arr addObject:[NSValue valueWithPoint:NSMakePoint(6, 7)]];
    [arr addObject:[NSValue valueWithPoint:NSMakePoint(8, 10)]];
    [arr addObject:[NSValue valueWithPoint:NSMakePoint(12, 16)]];
    
    NSValue *inserV = [NSValue valueWithPoint:NSMakePoint(4, 9)];

    NSInteger insertCount = 0;
    NSInteger i=0; //i最后停留在最后一个被合并的区间处(此时新区间应该插入的位置为:i-insertCount),或者新区间应该被插入的位置
    while (i < arr.count) {
        if (inserV.pointValue.y<[arr[i] pointValue].x) {
            break;
        }
        else if(inserV.pointValue.x>[arr[i] pointValue].y)
        {
            
        }
        else
        {
            NSPoint p = NSZeroPoint;
            p.x = inserV.pointValue.x<[arr[i] pointValue].x?inserV.pointValue.x:[arr[i] pointValue].x;
            p.y = inserV.pointValue.y>[arr[i] pointValue].y?inserV.pointValue.y:[arr[i] pointValue].y;
            inserV = [NSValue valueWithPoint:p];
            insertCount ++;
        }
        i++;
    }
    
    NSRange range = NSMakeRange(i - insertCount, insertCount);
    [arr removeObjectsInRange:range];
    [arr insertObject:inserV atIndex:i - insertCount];
    
    NSLog(@"%@",arr);
上一篇 下一篇

猜你喜欢

热点阅读