r*a
2 楼
问题1：你们买完鞋鞋盒子都扔么？堆了一柜子不好看又占地方，但是老担心以后搬家
问题2：刚才把冬天的鞋拿出来，发现基本都是boots啊，然后鞋架最上面一排满满的不
够放，下面几排基本都空着，高度不够。你们的鞋架都是啥样子的哇？
问题2：刚才把冬天的鞋拿出来，发现基本都是boots啊，然后鞋架最上面一排满满的不
够放，下面几排基本都空着，高度不够。你们的鞋架都是啥样子的哇？
s*x
3 楼
莫非要binary search找到？
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
c*e
4 楼
住大房子，然后这样
l*5
5 楼
貌似是先按interval的begin排序然后插？
s*x
6 楼
一般runtime超时是给time Exceeded Limit啥的，
现在说是timedout，就不知道该如何是好了。
网上找了个别人的解法也是timedout，是要用binary search做吗？
【在 l********5 的大作中提到】
: 貌似是先按interval的begin排序然后插？
现在说是timedout，就不知道该如何是好了。
网上找了个别人的解法也是timedout，是要用binary search做吗？
【在 l********5 的大作中提到】
: 貌似是先按interval的begin排序然后插？
s*x
7 楼
ding
【在 s********x 的大作中提到】
: 一般runtime超时是给time Exceeded Limit啥的，
: 现在说是timedout，就不知道该如何是好了。
: 网上找了个别人的解法也是timedout，是要用binary search做吗？
【在 s********x 的大作中提到】
: 一般runtime超时是给time Exceeded Limit啥的，
: 现在说是timedout，就不知道该如何是好了。
: 网上找了个别人的解法也是timedout，是要用binary search做吗？
y*e
8 楼
/*
Algorithm: Modified Binary search
[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
1. BSearch to find the 'first' interval whose end >= newInterval.start.
If does not find, the new interval should be appended at the tail.
2. BSearch to find the 'last' interval whose start <= newInterval.end.
If does not find, the new interval should be inserted before the head.
3. Erase the found 'first' to 'last' intervals and insert the new merged
interval at index 'first'
*/
vector insert(vector &intervals, Interval newInterval) {
int n = intervals.size();
if (n == 0) {
intervals.push_back(newInterval);
return intervals;
}
int first = -1, last = -1;// first and last interval to be merged/erased
int l = 0, r = n-1;
while (l < r) {
int m = (l+r)/2;
if (intervals[m].end >= newInterval.start)
r = m;
else
l = m+1;
}
first = intervals[l].end >= newInterval.start ? l : n;
l = 0, r = n-1;
while (l < r) {
int m = (l+r)/2+1;
if (intervals[m].start <= newInterval.end)
l = m;
else
r = m-1;
}
last = intervals[l].start <= newInterval.end ? l : -1;
if (first == n)
intervals.push_back(newInterval);
else if (last == -1)
intervals.insert(intervals.begin(), newInterval);
else {
//[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
int newStart = min(newInterval.start, intervals[first].start);
int newEnd = max(newInterval.end, intervals[last].end);
Interval merged(newStart, newEnd);
intervals.erase(intervals.begin()+first,intervals.begin()+last+1);
intervals.insert(intervals.begin()+first, merged);
}
return intervals;
}
Algorithm: Modified Binary search
[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
1. BSearch to find the 'first' interval whose end >= newInterval.start.
If does not find, the new interval should be appended at the tail.
2. BSearch to find the 'last' interval whose start <= newInterval.end.
If does not find, the new interval should be inserted before the head.
3. Erase the found 'first' to 'last' intervals and insert the new merged
interval at index 'first'
*/
vector
int n = intervals.size();
if (n == 0) {
intervals.push_back(newInterval);
return intervals;
}
int first = -1, last = -1;// first and last interval to be merged/erased
int l = 0, r = n-1;
while (l < r) {
int m = (l+r)/2;
if (intervals[m].end >= newInterval.start)
r = m;
else
l = m+1;
}
first = intervals[l].end >= newInterval.start ? l : n;
l = 0, r = n-1;
while (l < r) {
int m = (l+r)/2+1;
if (intervals[m].start <= newInterval.end)
l = m;
else
r = m-1;
}
last = intervals[l].start <= newInterval.end ? l : -1;
if (first == n)
intervals.push_back(newInterval);
else if (last == -1)
intervals.insert(intervals.begin(), newInterval);
else {
//[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
int newStart = min(newInterval.start, intervals[first].start);
int newEnd = max(newInterval.end, intervals[last].end);
Interval merged(newStart, newEnd);
intervals.erase(intervals.begin()+first,intervals.begin()+last+1);
intervals.insert(intervals.begin()+first, merged);
}
return intervals;
}
s*x
9 楼
非常感谢！
代码思路非常清楚！
可惜Java的ArrayList没有erase这样的function，不然可以更简洁。
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
代码思路非常清楚！
可惜Java的ArrayList没有erase这样的function，不然可以更简洁。
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
s*x
10 楼
ls的binary search还是有可以improve的地方，因为在hit到某个interval时search就
可以停止了，效率更高。我贴一些我的代码吧。思路是跟ls一样的。谢谢ls的代码。
public ArrayList insert(ArrayList intervals,
Interval newInterval) {
int n = intervals.size();
if (n==0) {
intervals.add(newInterval);
return intervals;
}
int first = -1, last = -1; // first and last interval to be merged/
erased
int l = 0, r = n - 1;
// BSearch to find the 'first' interval whose end >= newInterval.
start.
// If does not find, the new interval should be appended at the tail.
while (l < r) {
int m = l + ((r-l) >>> 1);
if (newInterval.start <= intervals.get(m).end) {
if (newInterval.start == intervals.get(m).end || m == 0 ||
intervals.get(m-1).end < newInterval.start) {
l = m;
break;
}
r = m - 1;
} else {
l = m + 1;
}
}
first = intervals.get(l).end >= newInterval.start ? l : n;
l = 0;
r = n - 1;
// BSearch to find the 'last' interval whose start <= newInterval.end.
// If does not find, the new interval should be inserted before the
head.
while (l < r) {
int m = l + ((r-l)>>>1);
if (intervals.get(m).start <= newInterval.end) {
if (intervals.get(m).start == newInterval.end || newInterval
.end < intervals.get(m+1).start) {
l = m;
break;
}
l = m + 1;
} else {
r = m - 1;
}
}
last = intervals.get(l).start <= newInterval.end ? l : -1;
if (first == n) {
intervals.add(newInterval);
} else if (last == -1) {
intervals.add(0, newInterval);
} else {
// Erase the found 'first' to 'last' intervals and insert the new
merged
// interval at index 'first'
int newStart = Math.min(newInterval.start, intervals.get(first).
start);
int newEnd = Math.max(newInterval.end, intervals.get(last).end);
Interval merged = new Interval(newStart, newEnd);
ArrayList tmp = new ArrayList();
for (int i = 0; i < first; i++) {
tmp.add(intervals.get(i));
}
tmp.add(merged);
for (int i = last + 1; i < intervals.size(); i++) {
tmp.add(intervals.get(i));
}
intervals = tmp;
}
return intervals;
}
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
可以停止了，效率更高。我贴一些我的代码吧。思路是跟ls一样的。谢谢ls的代码。
public ArrayList
Interval newInterval) {
int n = intervals.size();
if (n==0) {
intervals.add(newInterval);
return intervals;
}
int first = -1, last = -1; // first and last interval to be merged/
erased
int l = 0, r = n - 1;
// BSearch to find the 'first' interval whose end >= newInterval.
start.
// If does not find, the new interval should be appended at the tail.
while (l < r) {
int m = l + ((r-l) >>> 1);
if (newInterval.start <= intervals.get(m).end) {
if (newInterval.start == intervals.get(m).end || m == 0 ||
intervals.get(m-1).end < newInterval.start) {
l = m;
break;
}
r = m - 1;
} else {
l = m + 1;
}
}
first = intervals.get(l).end >= newInterval.start ? l : n;
l = 0;
r = n - 1;
// BSearch to find the 'last' interval whose start <= newInterval.end.
// If does not find, the new interval should be inserted before the
head.
while (l < r) {
int m = l + ((r-l)>>>1);
if (intervals.get(m).start <= newInterval.end) {
if (intervals.get(m).start == newInterval.end || newInterval
.end < intervals.get(m+1).start) {
l = m;
break;
}
l = m + 1;
} else {
r = m - 1;
}
}
last = intervals.get(l).start <= newInterval.end ? l : -1;
if (first == n) {
intervals.add(newInterval);
} else if (last == -1) {
intervals.add(0, newInterval);
} else {
// Erase the found 'first' to 'last' intervals and insert the new
merged
// interval at index 'first'
int newStart = Math.min(newInterval.start, intervals.get(first).
start);
int newEnd = Math.max(newInterval.end, intervals.get(last).end);
Interval merged = new Interval(newStart, newEnd);
ArrayList
for (int i = 0; i < first; i++) {
tmp.add(intervals.get(i));
}
tmp.add(merged);
for (int i = last + 1; i < intervals.size(); i++) {
tmp.add(intervals.get(i));
}
intervals = tmp;
}
return intervals;
}
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
n*a
11 楼
Timeout 不是程序的问题，是服务器太忙了。现在找工作季节，尤其到了晚上刷的人更
多，Timeout的话，等一会再交就好了
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
多，Timeout的话，等一会再交就好了
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
s*x
12 楼
试了下timedout，也不知是哪里有问题
有pass的人可以说说吗？
谢谢！
有pass的人可以说说吗？
谢谢！
s*x
13 楼
莫非要binary search找到？
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
l*5
14 楼
貌似是先按interval的begin排序然后插？
s*x
15 楼
一般runtime超时是给time Exceeded Limit啥的，
现在说是timedout，就不知道该如何是好了。
网上找了个别人的解法也是timedout，是要用binary search做吗？
【在 l********5 的大作中提到】
: 貌似是先按interval的begin排序然后插？
现在说是timedout，就不知道该如何是好了。
网上找了个别人的解法也是timedout，是要用binary search做吗？
【在 l********5 的大作中提到】
: 貌似是先按interval的begin排序然后插？
s*x
16 楼
ding
【在 s********x 的大作中提到】
: 一般runtime超时是给time Exceeded Limit啥的，
: 现在说是timedout，就不知道该如何是好了。
: 网上找了个别人的解法也是timedout，是要用binary search做吗？
【在 s********x 的大作中提到】
: 一般runtime超时是给time Exceeded Limit啥的，
: 现在说是timedout，就不知道该如何是好了。
: 网上找了个别人的解法也是timedout，是要用binary search做吗？
y*e
17 楼
/*
Algorithm: Modified Binary search
[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
1. BSearch to find the 'first' interval whose end >= newInterval.start.
If does not find, the new interval should be appended at the tail.
2. BSearch to find the 'last' interval whose start <= newInterval.end.
If does not find, the new interval should be inserted before the head.
3. Erase the found 'first' to 'last' intervals and insert the new merged
interval at index 'first'
*/
vector insert(vector &intervals, Interval newInterval) {
int n = intervals.size();
if (n == 0) {
intervals.push_back(newInterval);
return intervals;
}
int first = -1, last = -1;// first and last interval to be merged/erased
int l = 0, r = n-1;
while (l < r) {
int m = (l+r)/2;
if (intervals[m].end >= newInterval.start)
r = m;
else
l = m+1;
}
first = intervals[l].end >= newInterval.start ? l : n;
l = 0, r = n-1;
while (l < r) {
int m = (l+r)/2+1;
if (intervals[m].start <= newInterval.end)
l = m;
else
r = m-1;
}
last = intervals[l].start <= newInterval.end ? l : -1;
if (first == n)
intervals.push_back(newInterval);
else if (last == -1)
intervals.insert(intervals.begin(), newInterval);
else {
//[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
int newStart = min(newInterval.start, intervals[first].start);
int newEnd = max(newInterval.end, intervals[last].end);
Interval merged(newStart, newEnd);
intervals.erase(intervals.begin()+first,intervals.begin()+last+1);
intervals.insert(intervals.begin()+first, merged);
}
return intervals;
}
Algorithm: Modified Binary search
[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
1. BSearch to find the 'first' interval whose end >= newInterval.start.
If does not find, the new interval should be appended at the tail.
2. BSearch to find the 'last' interval whose start <= newInterval.end.
If does not find, the new interval should be inserted before the head.
3. Erase the found 'first' to 'last' intervals and insert the new merged
interval at index 'first'
*/
vector
int n = intervals.size();
if (n == 0) {
intervals.push_back(newInterval);
return intervals;
}
int first = -1, last = -1;// first and last interval to be merged/erased
int l = 0, r = n-1;
while (l < r) {
int m = (l+r)/2;
if (intervals[m].end >= newInterval.start)
r = m;
else
l = m+1;
}
first = intervals[l].end >= newInterval.start ? l : n;
l = 0, r = n-1;
while (l < r) {
int m = (l+r)/2+1;
if (intervals[m].start <= newInterval.end)
l = m;
else
r = m-1;
}
last = intervals[l].start <= newInterval.end ? l : -1;
if (first == n)
intervals.push_back(newInterval);
else if (last == -1)
intervals.insert(intervals.begin(), newInterval);
else {
//[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
int newStart = min(newInterval.start, intervals[first].start);
int newEnd = max(newInterval.end, intervals[last].end);
Interval merged(newStart, newEnd);
intervals.erase(intervals.begin()+first,intervals.begin()+last+1);
intervals.insert(intervals.begin()+first, merged);
}
return intervals;
}
s*x
18 楼
非常感谢！
代码思路非常清楚！
可惜Java的ArrayList没有erase这样的function，不然可以更简洁。
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
代码思路非常清楚！
可惜Java的ArrayList没有erase这样的function，不然可以更简洁。
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
s*x
19 楼
ls的binary search还是有可以improve的地方，因为在hit到某个interval时search就
可以停止了，效率更高。我贴一些我的代码吧。思路是跟ls一样的。谢谢ls的代码。
public ArrayList insert(ArrayList intervals,
Interval newInterval) {
int n = intervals.size();
if (n==0) {
intervals.add(newInterval);
return intervals;
}
int first = -1, last = -1; // first and last interval to be merged/
erased
int l = 0, r = n - 1;
// BSearch to find the 'first' interval whose end >= newInterval.
start.
// If does not find, the new interval should be appended at the tail.
while (l < r) {
int m = l + ((r-l) >>> 1);
if (newInterval.start <= intervals.get(m).end) {
if (newInterval.start == intervals.get(m).end || m == 0 ||
intervals.get(m-1).end < newInterval.start) {
l = m;
break;
}
r = m - 1;
} else {
l = m + 1;
}
}
first = intervals.get(l).end >= newInterval.start ? l : n;
l = 0;
r = n - 1;
// BSearch to find the 'last' interval whose start <= newInterval.end.
// If does not find, the new interval should be inserted before the
head.
while (l < r) {
int m = l + ((r-l)>>>1);
if (intervals.get(m).start <= newInterval.end) {
if (intervals.get(m).start == newInterval.end || newInterval
.end < intervals.get(m+1).start) {
l = m;
break;
}
l = m + 1;
} else {
r = m - 1;
}
}
last = intervals.get(l).start <= newInterval.end ? l : -1;
if (first == n) {
intervals.add(newInterval);
} else if (last == -1) {
intervals.add(0, newInterval);
} else {
// Erase the found 'first' to 'last' intervals and insert the new
merged
// interval at index 'first'
int newStart = Math.min(newInterval.start, intervals.get(first).
start);
int newEnd = Math.max(newInterval.end, intervals.get(last).end);
Interval merged = new Interval(newStart, newEnd);
ArrayList tmp = new ArrayList();
for (int i = 0; i < first; i++) {
tmp.add(intervals.get(i));
}
tmp.add(merged);
for (int i = last + 1; i < intervals.size(); i++) {
tmp.add(intervals.get(i));
}
intervals = tmp;
}
return intervals;
}
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
可以停止了，效率更高。我贴一些我的代码吧。思路是跟ls一样的。谢谢ls的代码。
public ArrayList
Interval newInterval) {
int n = intervals.size();
if (n==0) {
intervals.add(newInterval);
return intervals;
}
int first = -1, last = -1; // first and last interval to be merged/
erased
int l = 0, r = n - 1;
// BSearch to find the 'first' interval whose end >= newInterval.
start.
// If does not find, the new interval should be appended at the tail.
while (l < r) {
int m = l + ((r-l) >>> 1);
if (newInterval.start <= intervals.get(m).end) {
if (newInterval.start == intervals.get(m).end || m == 0 ||
intervals.get(m-1).end < newInterval.start) {
l = m;
break;
}
r = m - 1;
} else {
l = m + 1;
}
}
first = intervals.get(l).end >= newInterval.start ? l : n;
l = 0;
r = n - 1;
// BSearch to find the 'last' interval whose start <= newInterval.end.
// If does not find, the new interval should be inserted before the
head.
while (l < r) {
int m = l + ((r-l)>>>1);
if (intervals.get(m).start <= newInterval.end) {
if (intervals.get(m).start == newInterval.end || newInterval
.end < intervals.get(m+1).start) {
l = m;
break;
}
l = m + 1;
} else {
r = m - 1;
}
}
last = intervals.get(l).start <= newInterval.end ? l : -1;
if (first == n) {
intervals.add(newInterval);
} else if (last == -1) {
intervals.add(0, newInterval);
} else {
// Erase the found 'first' to 'last' intervals and insert the new
merged
// interval at index 'first'
int newStart = Math.min(newInterval.start, intervals.get(first).
start);
int newEnd = Math.max(newInterval.end, intervals.get(last).end);
Interval merged = new Interval(newStart, newEnd);
ArrayList
for (int i = 0; i < first; i++) {
tmp.add(intervals.get(i));
}
tmp.add(merged);
for (int i = last + 1; i < intervals.size(); i++) {
tmp.add(intervals.get(i));
}
intervals = tmp;
}
return intervals;
}
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
n*a
20 楼
Timeout 不是程序的问题，是服务器太忙了。现在找工作季节，尤其到了晚上刷的人更
多，Timeout的话，等一会再交就好了
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
多，Timeout的话，等一会再交就好了
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
l*2
21 楼
yixiuge的解法思路真清晰，我想请问一下你这题的binary search的那些 < , <= ，m
= (l+r)/2+1; m = (l+r)/2 这些，是如何把握的那么好从而没有off-by-one error的
？有没有什么技巧？
多谢
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
= (l+r)/2+1; m = (l+r)/2 这些，是如何把握的那么好从而没有off-by-one error的
？有没有什么技巧？
多谢
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
l*a
22 楼
以前看到一个办法，觉得挺好的，很清晰，不易出错
基本如下：
while(lo
if(a[mid]==**) break;
if(a[mid]>**) hi=mid;
else lo=mid;
}
这样结果就在lo..hi之间
最后lo=hi-1 , 判断一下a[lo],a[hi]是否满足要求就可以了
m
【在 l*******2 的大作中提到】
: yixiuge的解法思路真清晰，我想请问一下你这题的binary search的那些 < , <= ，m
: = (l+r)/2+1; m = (l+r)/2 这些，是如何把握的那么好从而没有off-by-one error的
: ？有没有什么技巧？
: 多谢
基本如下：
while(lo
if(a[mid]==**) break;
if(a[mid]>**) hi=mid;
else lo=mid;
}
这样结果就在lo..hi之间
最后lo=hi-1 , 判断一下a[lo],a[hi]是否满足要求就可以了
m
【在 l*******2 的大作中提到】
: yixiuge的解法思路真清晰，我想请问一下你这题的binary search的那些 < , <= ，m
: = (l+r)/2+1; m = (l+r)/2 这些，是如何把握的那么好从而没有off-by-one error的
: ？有没有什么技巧？
: 多谢
l*2
23 楼
yixiuge的解法思路真清晰，我想请问一下你这题的binary search的那些 < , <= ，m
= (l+r)/2+1; m = (l+r)/2 这些，是如何把握的那么好从而没有off-by-one error的
？有没有什么技巧？
多谢
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
= (l+r)/2+1; m = (l+r)/2 这些，是如何把握的那么好从而没有off-by-one error的
？有没有什么技巧？
多谢
【在 y*****e 的大作中提到】
: /*
: Algorithm: Modified Binary search
: [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
: 1. BSearch to find the 'first' interval whose end >= newInterval.start.
: If does not find, the new interval should be appended at the tail.
: 2. BSearch to find the 'last' interval whose start <= newInterval.end.
: If does not find, the new interval should be inserted before the head.
: 3. Erase the found 'first' to 'last' intervals and insert the new merged
: interval at index 'first'
: */
l*a
24 楼
以前看到一个办法，觉得挺好的，很清晰，不易出错
基本如下：
while(lo
if(a[mid]==**) break;
if(a[mid]>**) hi=mid;
else lo=mid;
}
这样结果就在lo..hi之间
最后lo=hi-1 , 判断一下a[lo],a[hi]是否满足要求就可以了
m
【在 l*******2 的大作中提到】
: yixiuge的解法思路真清晰，我想请问一下你这题的binary search的那些 < , <= ，m
: = (l+r)/2+1; m = (l+r)/2 这些，是如何把握的那么好从而没有off-by-one error的
: ？有没有什么技巧？
: 多谢
基本如下：
while(lo
if(a[mid]==**) break;
if(a[mid]>**) hi=mid;
else lo=mid;
}
这样结果就在lo..hi之间
最后lo=hi-1 , 判断一下a[lo],a[hi]是否满足要求就可以了
m
【在 l*******2 的大作中提到】
: yixiuge的解法思路真清晰，我想请问一下你这题的binary search的那些 < , <= ，m
: = (l+r)/2+1; m = (l+r)/2 这些，是如何把握的那么好从而没有off-by-one error的
: ？有没有什么技巧？
: 多谢
f*t
25 楼
class Intervals {
vector> _vals;
public:
Intervals(initializer_list> prs) {
_vals.insert(_vals.end(), prs.begin(), prs.end());
}
void Dump() {
for_each(_vals.begin(), _vals.end(), [](const pair &p) {
cout << '(' << p.first << ',' << p.second << ')' << ", ";
});
cout << endl;
}
void Insert(const pair &pr) {
auto left = lower_bound(_vals.begin(), _vals.end(), pr,
[](const pair &x, const pair &y) {
return x.second < y.first;
});
int lv = left == _vals.end() || pr.first < left->first ? pr.first : left
->first;
auto right = lower_bound(_vals.begin(), _vals.end(), pr,
[](const pair &x, const pair &y) {
return x.first < y.second;
});
if (right != _vals.end() && pr.second == right->first) {
++right;
}
int rv;
if (right != _vals.begin()) {
rv = max(pr.second, (right - 1)->second);
} else {
rv = pr.second;
}
if (left == _vals.end()) {
_vals.emplace_back(lv, rv);
} else {
left->first = lv;
left->second = rv;
_vals.erase(left + 1, right);
}
}
};
vector
public:
Intervals(initializer_list
_vals.insert(_vals.end(), prs.begin(), prs.end());
}
void Dump() {
for_each(_vals.begin(), _vals.end(), [](const pair
cout << '(' << p.first << ',' << p.second << ')' << ", ";
});
cout << endl;
}
void Insert(const pair
auto left = lower_bound(_vals.begin(), _vals.end(), pr,
[](const pair
return x.second < y.first;
});
int lv = left == _vals.end() || pr.first < left->first ? pr.first : left
->first;
auto right = lower_bound(_vals.begin(), _vals.end(), pr,
[](const pair
return x.first < y.second;
});
if (right != _vals.end() && pr.second == right->first) {
++right;
}
int rv;
if (right != _vals.begin()) {
rv = max(pr.second, (right - 1)->second);
} else {
rv = pr.second;
}
if (left == _vals.end()) {
_vals.emplace_back(lv, rv);
} else {
left->first = lv;
left->second = rv;
_vals.erase(left + 1, right);
}
}
};
h*c
26 楼
那应该按tick 算
相关阅读
请教 SEPHORA的fresh mask 日期好吗sephora 为啥还没开始？有人买过这款羽绒服吗请教：需要买这些东西，在哪里买好？Stuart Weitzman 的鞋子好不好问个穿鞋的问题。求购sephora 20%off code for non vib－$5cashmere 毛衣真的抗寒吗发文纪念+惊喜+第一个 LV大衣上沾的绒毛怎么办？需借鉴的例子：Paula Deen Fired: Food Network Cancels Show ( (转载)展示几条收集的时装项链粗腿胖脚UGGA&F这种行为算欺诈吧，怎么搞？确认一下，LV从来不打折对吧《天鵝湖》的長裙coach 25%off code大家在公司年终晚会的时候都穿什么样的裙子啊东西很乱的coach买哪款好啊【参加活动】今天出门的风衣