# O(log n) method with binary search and index mapping in C++

• ``````/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
int findPos(vector<Interval>& intervals, int t) {
// return x such that A(x) <= t < A(x+1)
if (t < intervals.begin()->start) return -1;
if (t > intervals.rbegin()->end) return intervals.size() * 2 - 1;
int l = 0, r = intervals.size() * 2 - 1;
#define A(i) ((i%2)?(intervals[i/2].end):(intervals[i/2].start))
while (l <= r) {
int m = l + (r-l)/2;
int v = A(m);
if (v > t) {
r = m-1;
} else if (v < t) {
l = m+1;
} else return m;
}
return r;
}
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
if (intervals.empty()) {
intervals.push_back(newInterval);
return intervals;
}
// (0, 1) (2, 3) (4 5) ...
// -1 0  1   2  3  4  5 ...
int spos = findPos(intervals, newInterval.start);
int epos = findPos(intervals, newInterval.end);
int rems, reme;

if (spos%2 && spos >= 0 && A(spos) == newInterval.start) {
spos--;
newInterval.start = A(spos);
}
if (epos%2==0 && epos < intervals.size()*2 && A(epos) == newInterval.end) {
epos++;
newInterval.end = A(epos);
}

//cout<<newInterval.start<<"--"<<newInterval.end<<endl;
//cout<<spos<<"--"<<epos<<endl;

if (spos % 2) {
if (epos % 2) {
rems = (spos+1)/2;
reme = (epos-1)/2;
} else {
rems = (spos+1)/2;
reme = (epos)/2;
newInterval.end = (intervals.begin()+reme)->end;
}
} else {
if (epos % 2) {
rems = (spos)/2;
reme = (epos-1)/2;
newInterval.start = (intervals.begin()+rems)->start;
} else {
rems = (spos)/2;
reme = (epos)/2;
newInterval.start = (intervals.begin()+rems)->start;
newInterval.end = (intervals.begin()+reme)->end;
}
}
//cout<<rems<<"--"<<reme<<endl;
intervals.erase(intervals.begin()+rems, intervals.begin()+reme+1);
intervals.insert(intervals.begin()+rems, newInterval);
return intervals;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.