i********s
发帖数: 133 | 1 题目：两个文件里面存着行程安排，开始时间以及结束时间，设计算法找所有
conflicts。
还没有看见人讨论这道题。直接的一一比较，复杂度是O(n2).
好像可以降到 O(nlogn + nK)，K是每个interval最多和另外一个文件中interval
conflict的次数。所以最坏情况下，还是O(n2),但average time，可能好很多。 | b********h
发帖数: 119 | 2 应该可以做到O（nlogn）吧。
1. 对所有inverval以起始时间排序 -> nlogn
2. 对每一个inverval，以他的结束时间在他后面所有的interval里binary search。找
到的那个interval前面的所有interval与其conflict。 -> nlogn | i********s
发帖数: 133 | 3 不知道我理解的是否正确。比如 intervals: [1, 2] [3, 4] [5, 6] [7, 8].
找与interval [5,7] 相交的interval，用你的方法是[1,2] [3,4] [5,6]? | z****n
发帖数: 1379 | 4 我面google时候的原题。。。
按开始时间排序，然后考察每个interval，用二分法，对于开始时间比当前interval早
的所有interval，考察其中结束时间最晚的interval（这步通过随时更新当前所有考察
过的interval的最晚结束时间可以做到O(1)查找），如果比当前考察的interval开始时
间晚，则找到conflict，否则必然没有conflict；对于开始时间比当前interval晚的所
有interval，只需考察下一个interval的开始时间是否早于当前interval的结束时间即
可，也是O(1)，所以总的复杂度就是排序的复杂度nlogn。
【在 i********s 的大作中提到】
: 题目：两个文件里面存着行程安排，开始时间以及结束时间，设计算法找所有
: conflicts。
: 还没有看见人讨论这道题。直接的一一比较，复杂度是O(n2).
: 好像可以降到 O(nlogn + nK)，K是每个interval最多和另外一个文件中interval
: conflict的次数。所以最坏情况下，还是O(n2),但average time，可能好很多。
| b********h
发帖数: 119 | 5
[5,7]应该和其他四个一起排序的。我有一个没考虑到，就是起始时间相同的interval
。但只要保证来自不同文件的所有起始时间相同的interval的相对顺序是一致的也就没
有问题了。比如
A文件
[1, 2] [3, 4] [5, 6] [7, 8]
B文件
[5,7] [7,9]
混合排序后
[1, 2] [3, 4] [5, 6] 【5，7】 [7, 8] 【7，9】
这个顺序所有A的interval都在B之前，所以对A的元素进行搜索。[1, 2] [3, 4]没有
conflict。[5,6]conflict with【5，7】，[7,8]conflict with【7，9】.
【在 i********s 的大作中提到】
: 不知道我理解的是否正确。比如 intervals: [1, 2] [3, 4] [5, 6] [7, 8].
: 找与interval [5,7] 相交的interval，用你的方法是[1,2] [3,4] [5,6]?
| c***2
发帖数: 838 | 6 We can still use hash?
1) convert all time spots into integer
2) modified hash: for (t1,t2), set all hash elements to 1 from t1 to t2
is this feasible? | l**********3
发帖数: 161 | 7 LZ的原题说要找到所有的conflicts，你的方法找到的好像只是临近
的conflicts吧？
【在 z****n 的大作中提到】
: 我面google时候的原题。。。
: 按开始时间排序，然后考察每个interval，用二分法，对于开始时间比当前interval早
: 的所有interval，考察其中结束时间最晚的interval（这步通过随时更新当前所有考察
: 过的interval的最晚结束时间可以做到O(1)查找），如果比当前考察的interval开始时
: 间晚，则找到conflict，否则必然没有conflict；对于开始时间比当前interval晚的所
: 有interval，只需考察下一个interval的开始时间是否早于当前interval的结束时间即
: 可，也是O(1)，所以总的复杂度就是排序的复杂度nlogn。
| j*****u
发帖数: 1133 | 8 没有仔细想，类似merge sort可不可以？
假设单个文件里没有conflict，分别按start time sort
然后2个pointer，分别向后移动直到有overlap
【在 i********s 的大作中提到】
: 题目：两个文件里面存着行程安排，开始时间以及结束时间，设计算法找所有
: conflicts。
: 还没有看见人讨论这道题。直接的一一比较，复杂度是O(n2).
: 好像可以降到 O(nlogn + nK)，K是每个interval最多和另外一个文件中interval
: conflict的次数。所以最坏情况下，还是O(n2),但average time，可能好很多。
| i********s
发帖数: 133 | 9 如果只找一个，这个应该是ok的。
如果找出所有的呢？
【在 z****n 的大作中提到】
: 我面google时候的原题。。。
: 按开始时间排序，然后考察每个interval，用二分法，对于开始时间比当前interval早
: 的所有interval，考察其中结束时间最晚的interval（这步通过随时更新当前所有考察
: 过的interval的最晚结束时间可以做到O(1)查找），如果比当前考察的interval开始时
: 间晚，则找到conflict，否则必然没有conflict；对于开始时间比当前interval晚的所
: 有interval，只需考察下一个interval的开始时间是否早于当前interval的结束时间即
: 可，也是O(1)，所以总的复杂度就是排序的复杂度nlogn。
| j********x
发帖数: 2330 | 10 come on, you should use segment tree... | | | f****g
发帖数: 313 | 11 We have two schedules S1&S2:
S1 = { , , ... }
S2 = { , , ... }
Assumptions:
1. S1&S2 are sorted by the starting time.
2. There are no conflicts in S1 and S2 itself.
Problem:
We try to find all the conflicts between these two schedules.
the basic idea is to merge sort to find the conflicts. the running time is
O(n).
My code in python: (code is kind of messy)
def merge(a,b):
i, j = 0, 0
unconflict = []
conflict = []
while( i < len(a) and j
if(a[i][0] <= b[j][0]):
add(a[i], unconflict, conflict)
i = i + 1
else:
add(b[j], unconflict, conflict)
j = j + 1
while(i < len(a)):
add(a[i], unconflict, conflict)
i = i + 1
while(j < len(b)):
add(b[j], unconflict, conflict)
j = j + 1
def add(p, unconflict, conflict):
if len(unconflict):
if p[0] < unconflict[-1][1] :
print("Conflicts between ", unconflict[-1], p)
if len(conflict):
if p[0] < conflict[-1][1]:
print("Conflicts between ",
conflict[-1], p)
else: conflict.append(p)
else: conflict.append(p)
else:
unconflict.append(p)
if len(conflict):
if p[0] < conflict[-1][1]:
print("Conflicts between ",
conflict[-1], p)
else: unconflict.append(p)
=========================
a = [(1,2), (4,5),(6,7),(8,9),(9,10),(11,23)]
b = [(1,3),(4,8),(8,11)]
merge(a,b)
Result:
Conflicts between (1, 2) (1, 3)
Conflicts between (4, 5) (4, 8)
Conflicts between (4, 8) (6, 7)
Conflicts between (8, 9) (8, 11)
Conflicts between (8, 11) (9, 10) | z****n
发帖数: 1379 | 12 恩，我这个是找出所有的与其他interval有重叠的interval，但是无法找出所有的重叠
的interval pair
比如i1：[1,8], i2:[2,7], i3:[3,4], i4:[5,6]
我这方法可以把i1，i2，i3和i4都标记为和其他某个interval有重叠
但是i2和i4这对重叠的pair我这方法无法标记出
【在 i********s 的大作中提到】
: 如果只找一个，这个应该是ok的。
: 如果找出所有的呢？
| b*****e
发帖数: 474 | 13 前提和 flydog MM 的一样， 用C++:
#include
#include
#include
using namespace std;
int has_conflict(vector >& s1, int i1,
vector >& s2, int i2) {
if ( s1[i1].first <= s2[i2].first && s2[i2].first < s1[i1].second
|| s2[i2].first <= s1[i1].first && s1[i1].first < s2[i2].second )
return 1;
return 0;
}
void print_conflict(vector >& s1, int i1,
vector >& s2, int i2) {
cout << "conflict between ["<< s1[i1].first <<","<< s1[i1].second
<< "] [" << s2[i2].first<< "," << s2[i2].second << "]" << endl;
}
void check_conflicts(vector >& s1, vector >& s2)
{
int l1 = s1.size();
int l2 = s2.size();
int i1 = 0;
int i2 = 0;
while ( i1 < l1 && i2 < l2 ) {
if ( has_conflict(s1,i1,s2,i2) ) print_conflict(s1,i1,s2,i2);
if ( s1[i1].second < s2[i2].second ) i1++ ;
else i2++;
}
}
int main(int argc, char *argv[]) {
vector > s1 ;
vector > s2;
s1.push_back(make_pair(1,2));
s1.push_back(make_pair(4,5));
s1.push_back(make_pair(6,7));
s1.push_back(make_pair(8,9));
s1.push_back(make_pair(9,10));
s1.push_back(make_pair(11,23));
s2.push_back(make_pair(1,3));
s2.push_back(make_pair(4,8));
s2.push_back(make_pair(8,11));
check_conflicts(s1, s2);
return 0;
} | i********s
发帖数: 133 | 14 在flydog MM的前提下，O(n)算法是存在的。但还有一个前提是要先sort。如果没有
sort，其实还是O(nlogn)的。
如果没有这个假设呢？（There are no conflicts in S1 and S2 itself.） | z****i
发帖数: 102 | 15 I think here we can use bitmap. Support it is one year, each hour is
indicated in a bit. We need 365*24/8 byptes. It is quite small.
Then scan A, set bits. Again, scan B, set conflicts if the bit is set
already.O(N) | J*******i
发帖数: 2162 | 16 这样做是nlogn么？我也想了这种做法
问题是虽然binary search到那个interval花的时间是logN
但是这样找到的所有conflict的interval也O(n)数量级的吧
每次把它们一一记录下来也是要花O(n)的时间吧？
比如一个worst case:
[1,m] [2,m] [3,m] ... [m-1,m]
【在 b********h 的大作中提到】
: 应该可以做到O（nlogn）吧。
: 1. 对所有inverval以起始时间排序 -> nlogn
: 2. 对每一个inverval，以他的结束时间在他后面所有的interval里binary search。找
: 到的那个interval前面的所有interval与其conflict。 -> nlogn
| l*********r
发帖数: 674 | 17 我的第一反应也是merge sort
【在 j*****u 的大作中提到】
: 没有仔细想，类似merge sort可不可以？
: 假设单个文件里没有conflict，分别按start time sort
: 然后2个pointer，分别向后移动直到有overlap
| b********h
发帖数: 119 | 18 一共N个interval，每个interval花费logN的时间，那总时间当然是NlogN了。
所有conflic是O（N）跟这个算法是NlogN好像不矛盾吧。
这道题有个很强的限制条件就是每个schedule自身不冲突，这样，任何一个interval，
它最多跟另一个schedule的所有interval冲突，而且，这个interval之后的那个
interval，最多就只能跟另一个schedule的最后一个interval冲突。楼上讨论出来的O
（N）算法就是基于这个条件的。
【在 J*******i 的大作中提到】
: 这样做是nlogn么？我也想了这种做法
: 问题是虽然binary search到那个interval花的时间是logN
: 但是这样找到的所有conflict的interval也O(n)数量级的吧
: 每次把它们一一记录下来也是要花O(n)的时间吧？
: 比如一个worst case:
: [1,m] [2,m] [3,m] ... [m-1,m]
| b**y
发帖数: 32 | 19 为什么排完序以后要用二分法，不是从头到尾扫描一遍就可以了吗？
【在 z****n 的大作中提到】
: 我面google时候的原题。。。
: 按开始时间排序，然后考察每个interval，用二分法，对于开始时间比当前interval早
: 的所有interval，考察其中结束时间最晚的interval（这步通过随时更新当前所有考察
: 过的interval的最晚结束时间可以做到O(1)查找），如果比当前考察的interval开始时
: 间晚，则找到conflict，否则必然没有conflict；对于开始时间比当前interval晚的所
: 有interval，只需考察下一个interval的开始时间是否早于当前interval的结束时间即
: 可，也是O(1)，所以总的复杂度就是排序的复杂度nlogn。
| c******n
发帖数: 4965 | 20 那是当然， 如果所有的时间段都是一样，那两两冲突，本身output 就是O(n)
你题目说错了吧， 应该是问max non-conflicting schedule, 就是CLRS 里面greedy
algorithm 一章的开篇
【在 i********s 的大作中提到】
: 题目：两个文件里面存着行程安排，开始时间以及结束时间，设计算法找所有
: conflicts。
: 还没有看见人讨论这道题。直接的一一比较，复杂度是O(n2).
: 好像可以降到 O(nlogn + nK)，K是每个interval最多和另外一个文件中interval
: conflict的次数。所以最坏情况下，还是O(n2),但average time，可能好很多。
| g*********s
发帖数: 1782 | 21 同一个文件里的行程互相不冲突？
【在 i********s 的大作中提到】
: 题目：两个文件里面存着行程安排，开始时间以及结束时间，设计算法找所有
: conflicts。
: 还没有看见人讨论这道题。直接的一一比较，复杂度是O(n2).
: 好像可以降到 O(nlogn + nK)，K是每个interval最多和另外一个文件中interval
: conflict的次数。所以最坏情况下，还是O(n2),但average time，可能好很多。
|
|
