1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126


#include <vector>
#include <iostream>
using namespace std;

struct Interval 
{
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};
 

int BSeachLowerBoundForStart(vector<Interval> &intervals, int start)
{
    if(intervals.size() <=0 || start <　intervals[0].start ) return -1;

    int low = 0;
    int high = intervals.size()-1;
    int mid = (low + high + 1) / 2;
    while(low < high)
    {
        if(start　<　intervals[mid].start)
            high = mid - 1;
        else
            low = mid;

        mid = (low + high + 1) / 2;
    }

    return mid;
}

int BSeachUpperBoundForEnd(vector<Interval> &intervals, int end)
{
    if(intervals.size() <=0 || intervals[intervals.size()-1].end < end) 
        return intervals.size();

    int low = 0;
    int high = intervals.size()-1;
    int mid = (low + high) / 2;
    while(low < high)
    {
        if(intervals[mid].end < end)
            low = mid + 1;
        else
            high = mid;

        mid = (low + high) / 2;
    }

    return mid;
}

vector<Interval> InsertInterval(vector<Interval> &intervals, Interval newInterval) 
{
    int low = BSeachLowerBoundForStart(intervals, newInterval.start);
    int high = BSeachUpperBoundForEnd(intervals, newInterval.end);

    //find the intervals in the contains that has been joined together,
    //in other words, those intervals would be removed
    if (low >=0 && intervals[low].end >= newInterval.start)
        newInterval.start = intervals[low].start;
    else
        low = low + 1; 

    if(high < intervals.size() && intervals[high].start <= newInterval.end)
        newInterval.end = intervals[high].end;
    else
        high = high - 1;
   

    vector<Interval> r;

    //get intervals from original conatiner
    int i = -1;
    while(++i<low)
        r.push_back(intervals[i]);
    
    //add new interval
    r.push_back(newInterval);

    //skip those removed intervals
    i = high;
    while(++i < intervals.size())
        r.push_back(intervals[i]);
	
	return	r;
}


using namespace std;

void PrintIntervals(vector<Interval>& v)
{
    for (int i = 0; i < v.size(); ++i)
        cout << '[' << v[i].start << ',' << v[i].end << "], ";
    
    cout << endl;
}


int main(int argc, char** argv)
{
    //[1,3],[6,9]; 
    vector<Interval> v1;
    v1.push_back(Interval(1,3));
    v1.push_back(Interval(6,9));

    vector<Interval> r1 = InsertInterval(v1, Interval(2,5));
    PrintIntervals(r1); //[1,5],[6,9]


    //[1,2],[3,5],[6,7],[8,10],[12,16]
    vector<Interval> v2;
    v2.push_back(Interval(1,2));
    v2.push_back(Interval(3,5));
    v2.push_back(Interval(6,7));
    v2.push_back(Interval(8,10));
    v2.push_back(Interval(12,16));

    vector<Interval> r2 = InsertInterval(v2, Interval(4,9));
    PrintIntervals(r2); //[1,2],[3,10],[12,16]

    return 0;
}
View Program Text


Test Status