s********x
发帖数: 914 | 1 试了下timedout，也不知是哪里有问题
有pass的人可以说说吗？
谢谢！ | s********x
发帖数: 914 | 2 莫非要binary search找到？
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
| l********5
发帖数: 230 | 3 貌似是先按interval的begin排序然后插？ | s********x
发帖数: 914 | 4 一般runtime超时是给time Exceeded Limit啥的，
现在说是timedout，就不知道该如何是好了。
网上找了个别人的解法也是timedout，是要用binary search做吗？
【在 l********5 的大作中提到】
: 貌似是先按interval的begin排序然后插？
| s********x
发帖数: 914 | 5 ding
【在 s********x 的大作中提到】
: 一般runtime超时是给time Exceeded Limit啥的，
: 现在说是timedout，就不知道该如何是好了。
: 网上找了个别人的解法也是timedout，是要用binary search做吗？
| y*****e
发帖数: 18 | 6 /*
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;
} | s********x
发帖数: 914 | 7 非常感谢！
代码思路非常清楚！
可惜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
发帖数: 914 | 8 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'
: */
| n*****a
发帖数: 107 | 9 Timeout 不是程序的问题，是服务器太忙了。现在找工作季节，尤其到了晚上刷的人更
多，Timeout的话，等一会再交就好了
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
| s********x
发帖数: 914 | 10 试了下timedout，也不知是哪里有问题
有pass的人可以说说吗？
谢谢！ | | | s********x
发帖数: 914 | 11 莫非要binary search找到？
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
| l********5
发帖数: 230 | 12 貌似是先按interval的begin排序然后插？ | s********x
发帖数: 914 | 13 一般runtime超时是给time Exceeded Limit啥的，
现在说是timedout，就不知道该如何是好了。
网上找了个别人的解法也是timedout，是要用binary search做吗？
【在 l********5 的大作中提到】
: 貌似是先按interval的begin排序然后插？
| s********x
发帖数: 914 | 14 ding
【在 s********x 的大作中提到】
: 一般runtime超时是给time Exceeded Limit啥的，
: 现在说是timedout，就不知道该如何是好了。
: 网上找了个别人的解法也是timedout，是要用binary search做吗？
| y*****e
发帖数: 18 | 15 /*
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;
} | s********x
发帖数: 914 | 16 非常感谢！
代码思路非常清楚！
可惜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
发帖数: 914 | 17 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'
: */
| n*****a
发帖数: 107 | 18 Timeout 不是程序的问题，是服务器太忙了。现在找工作季节，尤其到了晚上刷的人更
多，Timeout的话，等一会再交就好了
【在 s********x 的大作中提到】
: 试了下timedout，也不知是哪里有问题
: 有pass的人可以说说吗？
: 谢谢！
| l*******2
发帖数: 36 | 19 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*****a
发帖数: 14598 | 20 以前看到一个办法，觉得挺好的，很清晰，不易出错
基本如下：
while(lo
mid=lo+(hi-lo)>>1;
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
发帖数: 36 | 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*****a
发帖数: 14598 | 22 以前看到一个办法，觉得挺好的，很清晰，不易出错
基本如下：
while(lo
mid=lo+(hi-lo)>>1;
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
发帖数: 1001 | 23 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);
}
}
}; | h**********c
发帖数: 4120 | |
|
