a******t
发帖数: 34 | 1 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. | s*********t
发帖数: 1663 | 2 不许排序？
想想。。
than
【在 a******t 的大作中提到】
: 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.
| s*********t
发帖数: 1663 | 3 似乎会了
bitmap
遍历输入，将所有覆盖的bit标记
标记操作是o(1)的
之后输出
than
【在 a******t 的大作中提到】
: 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.
| s*********t
发帖数: 1663 | 4 前提是都是整数。。。
【在 s*********t 的大作中提到】
: 似乎会了
: bitmap
: 遍历输入，将所有覆盖的bit标记
: 标记操作是o(1)的
: 之后输出
:
: than
| l******c
发帖数: 2555 | 5 什麽是bitmap， 是STL 里的吗
【在 s*********t 的大作中提到】
: 似乎会了
: bitmap
: 遍历输入，将所有覆盖的bit标记
: 标记操作是o(1)的
: 之后输出
:
: than
| m****u
发帖数: 3915 | 6 这个不对吧
他的n应该是number of pairs
你的n是range of pairs
比如输入是：[0 100] [2 3]
应该用O(2)的方法，你那是O(100)的方法
【在 s*********t 的大作中提到】
: 似乎会了
: bitmap
: 遍历输入，将所有覆盖的bit标记
: 标记操作是o(1)的
: 之后输出
:
: than
| s*********t
发帖数: 1663 | 7 不熟悉STL，STL里似乎叫bitset
【在 l******c 的大作中提到】
: 什麽是bitmap， 是STL 里的吗
| s*********t
发帖数: 1663 | 8 标记一个区间的操作应该是O(1)的
【在 m****u 的大作中提到】
: 这个不对吧
: 他的n应该是number of pairs
: 你的n是range of pairs
: 比如输入是：[0 100] [2 3]
: 应该用O(2)的方法，你那是O(100)的方法
| m****u
发帖数: 3915 | 9 标记是O(1),可是你取出merge后的区间如何做到O(1)?
【在 s*********t 的大作中提到】
: 标记一个区间的操作应该是O(1)的
| s*********t
发帖数: 1663 | 10 哦。。。对。。
那是在是不会了
【在 m****u 的大作中提到】
: 标记是O(1),可是你取出merge后的区间如何做到O(1)?
| | | m****u
发帖数: 3915 | 11 我也不会，坐等高人解答
【在 s*********t 的大作中提到】
: 哦。。。对。。
: 那是在是不会了
| c******f
发帖数: 2144 | 12 use an array to simulate the bitset?
【在 s*********t 的大作中提到】
: 似乎会了
: bitmap
: 遍历输入，将所有覆盖的bit标记
: 标记操作是o(1)的
: 之后输出
:
: than
| r****o
发帖数: 1950 | 13 能不能看看我的想法怎么样。
整数派序可以做到O(n),在[min..max]上每个点做个标记，然后取标记点就排好序了。
以第2个例子为例
把数组的每个first one排序， -3, 1, 4, 5, 8
再把每个second one排序， 0, 3, 6, 7, 9
从1..n, 如果second[i]
如果second[i]>first[i+1]，则first[i]和second[i+1]为一对。
最后输出(-3,0), (1,3), (4,7), (8,9).
than
【在 a******t 的大作中提到】
: 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.
| g*****u
发帖数: 298 | 14 这个有问题。如果你把输入的(5,7)改为(0,7)，就不对了。
我的做法是，
1. 只排序n个起始点，用bitmap，O(n)
2. 然后一个区间一个区间的进行合并，O(n)
第一步如果范围太大会占用过多空间，而且需要初始化。
如果题目要求不能用排序，暂时还没想到办法。
【在 r****o 的大作中提到】
: 能不能看看我的想法怎么样。
: 整数派序可以做到O(n),在[min..max]上每个点做个标记，然后取标记点就排好序了。
: 以第2个例子为例
: 把数组的每个first one排序， -3, 1, 4, 5, 8
: 再把每个second one排序， 0, 3, 6, 7, 9
: 从1..n, 如果second[i]: 如果second[i]>first[i+1]，则first[i]和second[i+1]为一对。
: 最后输出(-3,0), (1,3), (4,7), (8,9).
:
: than
| r****o
发帖数: 1950 | 15 我的想法也是一个一个区间合并，如果second[i]>＝first[i+1]则合并到前一个区间。
把输入改为(0.7)的话，结果是(-3,7)和(8,9).
如果只排序n个起始点的话，你是怎么合并区间的呢？
【在 g*****u 的大作中提到】
: 这个有问题。如果你把输入的(5,7)改为(0,7)，就不对了。
: 我的做法是，
: 1. 只排序n个起始点，用bitmap，O(n)
: 2. 然后一个区间一个区间的进行合并，O(n)
: 第一步如果范围太大会占用过多空间，而且需要初始化。
: 如果题目要求不能用排序，暂时还没想到办法。
| l******c
发帖数: 2555 | 16 如果有O(n)的排序方法， 这个问题就非常简单了。
按照 x 排序放入 数组a， 对应y放入数组b， 两个指针比较急可。
问题是有O(n)的排序算法吗？
【在 g*****u 的大作中提到】
: 这个有问题。如果你把输入的(5,7)改为(0,7)，就不对了。
: 我的做法是，
: 1. 只排序n个起始点，用bitmap，O(n)
: 2. 然后一个区间一个区间的进行合并，O(n)
: 第一步如果范围太大会占用过多空间，而且需要初始化。
: 如果题目要求不能用排序，暂时还没想到办法。
| r****o
发帖数: 1950 | 17 bitmap啊，
你说的两个指针比较能不能再详细说说?
【在 l******c 的大作中提到】
: 如果有O(n)的排序方法， 这个问题就非常简单了。
: 按照 x 排序放入 数组a， 对应y放入数组b， 两个指针比较急可。
: 问题是有O(n)的排序算法吗？
| l******c
发帖数: 2555 | 18 a 数组排序第一个元素， b 数组放另一元素
if b[i] > a[i+1]
cross out b[i] and a[i+1]
else
no overlap.
O(n) compare and output.
什麽是bitmap 排序？
【在 r****o 的大作中提到】
: bitmap啊，
: 你说的两个指针比较能不能再详细说说?
| r****o
发帖数: 1950 | 19 多谢。那你的b[]要排序吗？我觉得b[]要排序。
bitmap就是在坐标轴上对相应的元素作标记把。
【在 l******c 的大作中提到】
: a 数组排序第一个元素， b 数组放另一元素
: if b[i] > a[i+1]
: cross out b[i] and a[i+1]
: else
: no overlap.
: O(n) compare and output.
: 什麽是bitmap 排序？
| l******c
发帖数: 2555 | 20 b[] depends on a[], no sorting needed
【在 r****o 的大作中提到】
: 多谢。那你的b[]要排序吗？我觉得b[]要排序。
: bitmap就是在坐标轴上对相应的元素作标记把。
| | | r****o
发帖数: 1950 | 21 不知道是不是我理解错了。
那看看例子2
(-3,0) (8,9) (4,6) (1,3) (0,7)
a数组排序后 a[]={-3,0,1,4,8}
b[]={ 0,7,3,6,9}
你的程序是不是会输出(-3,0) (0,3) (4,6) (8,9)?
但我觉得是(-3,0) (0,7) (8,9).
【在 l******c 的大作中提到】
: a 数组排序第一个元素， b 数组放另一元素
: if b[i] > a[i+1]
: cross out b[i] and a[i+1]
: else
: no overlap.
: O(n) compare and output.
: 什麽是bitmap 排序？
| k*n
发帖数: 150 | 22 interval tree
than
【在 a******t 的大作中提到】
: 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.
| s*********t
发帖数: 1663 | 23 interval tree也不是O(n)吧？
【在 k*n 的大作中提到】
: interval tree
:
: than
| k*n
发帖数: 150 | 24 没看到o(n)，再看看
【在 s*********t 的大作中提到】
: interval tree也不是O(n)吧？
| l******c
发帖数: 2555 | 25 是有问题， 不过这bitmap sorting 就是大空间法， 时间等于range， 不是个数。
有一百对元素， range是 -10000 到 10000， 显然不对 需两万比较
【在 r****o 的大作中提到】
: 不知道是不是我理解错了。
: 那看看例子2
: (-3,0) (8,9) (4,6) (1,3) (0,7)
: a数组排序后 a[]={-3,0,1,4,8}
: b[]={ 0,7,3,6,9}
: 你的程序是不是会输出(-3,0) (0,3) (4,6) (8,9)?
: 但我觉得是(-3,0) (0,7) (8,9).
| y**i
发帖数: 1112 | 26 这种情况我觉得应该在他的那个算法里加入一个判断，如果b[i]>a[i+1]（这里7>1），
那么输出(a[i],max(b[i], b[i+1]))，重叠是肯定有了，但是输出区域应该是从符合这
个范围的a里面最小的数到b里面最大的数，a[i]肯定是最小的，因为已经按照a排序了
，但是b还需要在输出前判断一下。
另外，不是有一些O(n)排序的算法么，比如计数排序，基数排序什么的，如果在n很大
的情况下，能不能用呢？
【在 r****o 的大作中提到】
: 不知道是不是我理解错了。
: 那看看例子2
: (-3,0) (8,9) (4,6) (1,3) (0,7)
: a数组排序后 a[]={-3,0,1,4,8}
: b[]={ 0,7,3,6,9}
: 你的程序是不是会输出(-3,0) (0,3) (4,6) (8,9)?
: 但我觉得是(-3,0) (0,7) (8,9).
| r****o
发帖数: 1950 | 27 为啥都不说对b[]排序呢？
对b[]排序后不就不用管b[i]和b[i+1]哪个大了吗？
【在 y**i 的大作中提到】
: 这种情况我觉得应该在他的那个算法里加入一个判断，如果b[i]>a[i+1]（这里7>1），
: 那么输出(a[i],max(b[i], b[i+1]))，重叠是肯定有了，但是输出区域应该是从符合这
: 个范围的a里面最小的数到b里面最大的数，a[i]肯定是最小的，因为已经按照a排序了
: ，但是b还需要在输出前判断一下。
: 另外，不是有一些O(n)排序的算法么，比如计数排序，基数排序什么的，如果在n很大
: 的情况下，能不能用呢？
|
|
