Monday, November 25, 2013

LeetCode Problem : Insert Interval

Problem


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].

Code

int find_l(const vector<Interval> &intervals,int n,int x)
{
    int l = 1,r = n;
    while(l <= r){
        int m = (l + r)/2;
        if(x < intervals[m - 1].start)
            r = m - 1;
        else if(x > intervals[m - 1].end)
            l = m + 1;
        else
            return (m - 2);
    }
    if(l == n + 1)
        return n - 1;
    else if( r == 0)
        return -1;
    else if(x > intervals[l - 1].end)
        return l - 1;
    else if(x < intervals[r - 1].start)
        return r - 2;
    return r - 1;
}

int find_r(const vector<Interval> &intervals,int n,int x)
{
    int l = 1,r = n;
    while(l <= r){
        int m = (l + r)/2;
        if(x < intervals[m - 1].start)
            r = m - 1;
        else if(x > intervals[m - 1].end)
            l = m + 1;
        else
            return (m);
    }
    if(l == n + 1)
        return n;
    else if( r == 0)
        return 0;
    else if(x > intervals[l - 1].end)
        return l;
    else if(x < intervals[r - 1].start)
        return r - 1;
    return r;
}
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    vector<Interval> result;
    int n = intervals.size();   
    int l = find_l(intervals,n,newInterval.start);
    int r = find_r(intervals,n,newInterval.end);
    for(int i = 0; i <= l; ++i)
    result.push_back(intervals[i]);
    if(r == l + 1){
        result.push_back(Interval(newInterval.start,newInterval.end));
    }
    else{
        int left,right;
        if(l == n-1)
            left = newInterval.start;
        else
            left = min(newInterval.start,intervals[l + 1].start);
        if(r == 0)
            right = newInterval.end;
        else
            right = max(newInterval.end,intervals[r - 1].end);
        result.push_back(Interval(left,right));
    }
    for(int i = r; i < n; ++i)
        result.push_back(intervals[i]);
    return result;

}

No comments:

Post a Comment