s*****r
发帖数: 773 | 1 一个很小的公司, 要我一个小时写个程序发过去, 用了一个很simple的算法,就是从给
定range的每个integer对比一个range一个range的看, 大家看看这题如果要efficient
怎么弄?
Write a function that takes a list of integer ranges and an additional range
and prints all non-overlapping ranges from the additional range.
For example, given a list or ranges [6 – 10], [17 – 24], [15 – 19] and a
new range [8 – 28], your function should print [11 – 14], [25 - 28]. | c*********n
发帖数: 1057 | 2 根据第一个数排序，然后一个个range往后比对，维护一个global right bound，
每次都把这个right bound和rang的left value比较就好了吧？
efficient
range
a
【在 s*****r 的大作中提到】
: 一个很小的公司, 要我一个小时写个程序发过去, 用了一个很simple的算法,就是从给
: 定range的每个integer对比一个range一个range的看, 大家看看这题如果要efficient
: 怎么弄?
: Write a function that takes a list of integer ranges and an additional range
: and prints all non-overlapping ranges from the additional range.
: For example, given a list or ranges [6 – 10], [17 – 24], [15 – 19] and a
: new range [8 – 28], your function should print [11 – 14], [25 - 28].
| m******9
发帖数: 968 | 3 我的思路是这样的
1. 把new range [8,28] dump到数组A中，使得A[index] = index, 如果没有出现的
value，则设置为-1，即：
分配一个size=29的数组，[8,28]dump到该数组的结果就是：
A[-1,-1,-1,...-1,8,9,10,11,.....28]
2. 一次遍历list of ranges, 凡是能够在A中能够找到的value全部都设定为A[index]=
-1.
例如：对比[6,10]时， A[6]=-1, A[7]=-1; ... A[10]=-1
这样把整个range都遍历完
3. 再次遍历数组A，将A[index]!=-1的全部打印出来 | c*********n
发帖数: 1057 | 4 en这个时间上更快
]=
【在 m******9 的大作中提到】
: 我的思路是这样的
: 1. 把new range [8,28] dump到数组A中，使得A[index] = index, 如果没有出现的
: value，则设置为-1，即：
: 分配一个size=29的数组，[8,28]dump到该数组的结果就是：
: A[-1,-1,-1,...-1,8,9,10,11,.....28]
: 2. 一次遍历list of ranges, 凡是能够在A中能够找到的value全部都设定为A[index]=
: -1.
: 例如：对比[6,10]时， A[6]=-1, A[7]=-1; ... A[10]=-1
: 这样把整个range都遍历完
: 3. 再次遍历数组A，将A[index]!=-1的全部打印出来
| s*****r
发帖数: 773 | 5 这样还是要一个个遍历所有的range, 有没有不需要一个个range遍历的.
另外, 最开始的数组都没有用, 直接for loop 从begin开始到end, 一个个查是否在
range就行了.
]=
【在 m******9 的大作中提到】
: 我的思路是这样的
: 1. 把new range [8,28] dump到数组A中，使得A[index] = index, 如果没有出现的
: value，则设置为-1，即：
: 分配一个size=29的数组，[8,28]dump到该数组的结果就是：
: A[-1,-1,-1,...-1,8,9,10,11,.....28]
: 2. 一次遍历list of ranges, 凡是能够在A中能够找到的value全部都设定为A[index]=
: -1.
: 例如：对比[6,10]时， A[6]=-1, A[7]=-1; ... A[10]=-1
: 这样把整个range都遍历完
: 3. 再次遍历数组A，将A[index]!=-1的全部打印出来
| m******9
发帖数: 968 | 6 嗯，你说的没错，我弄错了。题目是只给个range就够了，并不是一组数。肯定有更好
的方法。
【在 s*****r 的大作中提到】
: 这样还是要一个个遍历所有的range, 有没有不需要一个个range遍历的.
: 另外, 最开始的数组都没有用, 直接for loop 从begin开始到end, 一个个查是否在
: range就行了.
:
: ]=
| z**k
发帖数: 629 | 7 应该先简化第一个Range系列,然后只比较其begin和end,不应该一一遍历. | k***e
发帖数: 556 | 8 range tree
i don't remember the exact name.
Computational Geometry Algorithms and Applications, chapter 10
nlgn preprocessing, O(lgn+matched#)
efficient
range
a
【在 s*****r 的大作中提到】
: 一个很小的公司, 要我一个小时写个程序发过去, 用了一个很simple的算法,就是从给
: 定range的每个integer对比一个range一个range的看, 大家看看这题如果要efficient
: 怎么弄?
: Write a function that takes a list of integer ranges and an additional range
: and prints all non-overlapping ranges from the additional range.
: For example, given a list or ranges [6 – 10], [17 – 24], [15 – 19] and a
: new range [8 – 28], your function should print [11 – 14], [25 - 28].
| m*****f
发帖数: 1243 | 9 I think the basic idea is sort the range number first by nlogn, then use
binary search to find the two range ends in the sorted list, so you don't
have to check the whole list
just O(logn) + O(matched)
【在 k***e 的大作中提到】
: range tree
: i don't remember the exact name.
: Computational Geometry Algorithms and Applications, chapter 10
: nlgn preprocessing, O(lgn+matched#)
:
: efficient
: range
: a
| x***y
发帖数: 633 | 10 1. Sort the lower boundary, and the upper boundary separately (O(nlogn)),
from the smallest lower boundary min_low (6 in your e.g), and assume upp is
the upper boundary corresponding(10 in e.g) to lower boundary, set old_upp
to min_low;
2. find position of upp in the array of lower boundary, and in the lower
boundary for all the values less than upp, if the largest corresponding
upper bound is bigger than upp, set old_upp to upp and set upp to the
largest corresponding upper bound, and do step
【在 s*****r 的大作中提到】
: 一个很小的公司, 要我一个小时写个程序发过去, 用了一个很simple的算法,就是从给
: 定range的每个integer对比一个range一个range的看, 大家看看这题如果要efficient
: 怎么弄?
: Write a function that takes a list of integer ranges and an additional range
: and prints all non-overlapping ranges from the additional range.
: For example, given a list or ranges [6 – 10], [17 – 24], [15 – 19] and a
: new range [8 – 28], your function should print [11 – 14], [25 - 28].
|
|
