H*M
发帖数: 1268 | 1 也是一个google题目
Input several pairs of numbers. The second number in the pair is larger than
the first one. You need to combine the intervals has overlap. eg:
Input: [1 3] [2 4] [5 6]
Output should be [1 4] [5 6]
Another eg: [-3 0] [8 9] [4 6] [1 3] [5 7]
output: [-3 0] [8 9] [1 3] [4 7]
Looking for a O(n) solution.
O(n)的办法没想出来,是o(nlgn)算法
连想加调试的时候花了差不多一小时。小错不断。苦死。
大家想想有没有什么好的O(n)办法吧。
另外我提醒大家，vector你要想erase好几个位置的元素的话，要注意shift.. |
g*******y
发帖数: 1930 | 2 速度只有靠多练习啊
你见过10分钟解难题并实现高效maxflow通过测试的牛人吗？人家那也是练了无数年的
功力啊
btw，我觉得这题就general case而言, nlogn就不错了吧？得sort一次吧？ |
H*M
发帖数: 1268 | 3 对,就是先sort一次,后面就好弄了
但是后面的一些coding循环处理细节花了时间
假如radix sort算O(n)的话,就是O(n), lol
【在 g*******y 的大作中提到】
: 速度只有靠多练习啊
: 你见过10分钟解难题并实现高效maxflow通过测试的牛人吗？人家那也是练了无数年的
: 功力啊
: btw，我觉得这题就general case而言, nlogn就不错了吧？得sort一次吧？
|
w********p
发帖数: 948 | 4 额觉着类似greedy algorithm里schedule的题
先按第一个值排序（O(n) or O(nlgn))， 然后比较二个值得value ( O(n) )
不过一个小时写radix我觉得很牛乐。 |
H*M
发帖数: 1268 | 5 你都排序了
【在 w********p 的大作中提到】
: 额觉着类似greedy algorithm里schedule的题
: 先按第一个值排序（O(n) or O(nlgn))， 然后比较二个值得value ( O(n) )
: 不过一个小时写radix我觉得很牛乐。
|
w********p
发帖数: 948 | 6 所以要O(n)的话，只能用radix的variation. 额是没法1hr高定
【在 H*M 的大作中提到】
: 你都排序了
|
k***e
发帖数: 556 | 7 10分钟，写个测试的case俺都要搞10分钟。看来是bill joy之类的人物。
【在 g*******y 的大作中提到】
: 速度只有靠多练习啊
: 你见过10分钟解难题并实现高效maxflow通过测试的牛人吗？人家那也是练了无数年的
: 功力啊
: btw，我觉得这题就general case而言, nlogn就不错了吧？得sort一次吧？
|
a****n
发帖数: 1887 | 8 check 线段树(internal tree) |
H*M
发帖数: 1268 | 9 u mean interval tree
doesn't apply here
or too complicated for such simple stuff
【在 a****n 的大作中提到】
: check 线段树(internal tree)
|
a****n
发帖数: 1887 | |
|
|
H*M
发帖数: 1268 | 11 u have to build the tree first
【在 a****n 的大作中提到】
: ...实现不是很麻烦, 和二叉树差不多
|
g*******y
发帖数: 1930 | 12 ACRush不知道你听过没有，清华的楼天成，coding界的王者人物。
【在 k***e 的大作中提到】
: 10分钟，写个测试的case俺都要搞10分钟。看来是bill joy之类的人物。
|
H*M
发帖数: 1268 | 13 ? you dont need to be him
【在 g*******y 的大作中提到】
: ACRush不知道你听过没有，清华的楼天成，coding界的王者人物。
|
g*******y
发帖数: 1930 | 14 就是很葱白而已，呵呵
【在 H*M 的大作中提到】
: ? you dont need to be him
|
x******e
发帖数: 13 | 15 bitmap should give you a O(n) solution if all numbers are integer.
1. find min and max of all the input integers. O(n)
2. define a binary array in the range of [min, max] (or binary map)
3. when reading each pair of integers [a, b], set the bits between a and b
to 1 if they are 0s. - O(n)
4. finally, scan the bitmap and output the continuous region. O(n).
I didn't implement it, but it should work for integer inputs. If any number
is not integer, the method doesn't work.
Any comments? |
g*******y
发帖数: 1930 | 16 might works well in special cases, but in general might not be a good method
This is what we call pseudo polynomial complexity.
number
【在 x******e 的大作中提到】
: bitmap should give you a O(n) solution if all numbers are integer.
: 1. find min and max of all the input integers. O(n)
: 2. define a binary array in the range of [min, max] (or binary map)
: 3. when reading each pair of integers [a, b], set the bits between a and b
: to 1 if they are 0s. - O(n)
: 4. finally, scan the bitmap and output the continuous region. O(n).
: I didn't implement it, but it should work for integer inputs. If any number
: is not integer, the method doesn't work.
: Any comments?
|
k***e
发帖数: 556 | 17 居然还是杭14中毕业的？真的没的听说过这个学校。
看来对钱没什么兴趣啊，不然不会读博士了。对于有追求的人，我也很葱白。
【在 H*M 的大作中提到】
: ? you dont need to be him
|
a*****e
发帖数: 51 | 18 This is actually a good solution after a little modification.
the complexity of step 3 is O(n^2) instead of O(n).
modifications:
step 2: instead of defining a binary array, define a byte array A, of size
max-min+1.
step3: when reading each pair of integers [a,b], set A[a-min]=1 and A[b-min]
=2;
step 4: Set a variable B=0. Scan array A from beginning. Whenever meet 1,B++
(When B==1, start recording a new interval). Whenever meet 2, B-- (When B==
0, conclude an interval).
number
【在 x******e 的大作中提到】
: bitmap should give you a O(n) solution if all numbers are integer.
: 1. find min and max of all the input integers. O(n)
: 2. define a binary array in the range of [min, max] (or binary map)
: 3. when reading each pair of integers [a, b], set the bits between a and b
: to 1 if they are 0s. - O(n)
: 4. finally, scan the bitmap and output the continuous region. O(n).
: I didn't implement it, but it should work for integer inputs. If any number
: is not integer, the method doesn't work.
: Any comments?
|
g*******y
发帖数: 1930 | 19 虽然你的方法挺巧的，不过：
按照这种byte array，size=max-min的，本身就实现了一种counting sort了
这个跟sort了之后再greedy的方法，其实没有起到什么优化啊
min]
++
==
【在 a*****e 的大作中提到】
: This is actually a good solution after a little modification.
: the complexity of step 3 is O(n^2) instead of O(n).
: modifications:
: step 2: instead of defining a binary array, define a byte array A, of size
: max-min+1.
: step3: when reading each pair of integers [a,b], set A[a-min]=1 and A[b-min]
: =2;
: step 4: Set a variable B=0. Scan array A from beginning. Whenever meet 1,B++
: (When B==1, start recording a new interval). Whenever meet 2, B-- (When B==
: 0, conclude an interval).
|
