t**********h
发帖数: 2273 | 1 Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
大牛们，这题能O（n）么？想不出啊 | l******e
发帖数: 149 | 2 if the collection is sorted at the first place.
【在 t**********h 的大作中提到】
: Merge Intervals
: Given a collection of intervals, merge all overlapping intervals.
: For example,
: Given [1,3],[2,6],[8,10],[15,18],
: return [1,6],[8,10],[15,18].
: 大牛们，这题能O（n）么？想不出啊
| t**********h
发帖数: 2273 | 3 我擦，原题没说有序
【在 l******e 的大作中提到】
: if the collection is sorted at the first place.
| S******6
发帖数: 55 | | t**********h
发帖数: 2273 | 5 sort就是 nlogn了啊
【在 S******6 的大作中提到】
: 先sort，O（N）可以
| b**********5
发帖数: 7881 | 6 那就是没有！
【在 t**********h 的大作中提到】
: sort就是 nlogn了啊
| z********o
发帖数: 4284 | 7 if starting points end points can be sorted in o(n), then its possible.
counting sort is o(n), for example, but values need to be in a range.
【在 t**********h 的大作中提到】
: Merge Intervals
: Given a collection of intervals, merge all overlapping intervals.
: For example,
: Given [1,3],[2,6],[8,10],[15,18],
: return [1,6],[8,10],[15,18].
: 大牛们，这题能O（n）么？想不出啊
| w*********m
发帖数: 4740 | 8 bucket sort
【在 z********o 的大作中提到】
: if starting points end points can be sorted in o(n), then its possible.
: counting sort is o(n), for example, but values need to be in a range.
| p*****2
发帖数: 21240 | 9 (reverse (reduce (fn [a, b] (if (and (first a) (>= (last (first a)) (first b
))) (cons (assoc (first a) 1 (last b)) (rest a)) (cons b a))) () '([1,3] [2,
6] [8,10] [15,18])))
|
|
