菜鸟也来问一个关于油烟机选择的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

菜鸟也来问一个关于油烟机选择的问题

菜鸟也来问一个关于油烟机选择的问题# Living

v*y2014-09-04 07:09

1 楼

========题目=======
公司里有好多employee，给出入职和离职的时间段，打印出每个时间段的在职人数
输入：
［1, 2005, 2016］
［2, 2008, 2014］
［3, 2006, 2008］
［4, 2010, 2014］
输出:
2005-2006: 1
2006-2008: 2
2008-2010: 2
2010-2014: 3
2014-2016: 1
======解法分割线=======
目前只想到下面这个方法，不知道大家有没有更好的解法？
step 1. 把员工数据按入职时间排个序得到数组S1，然后按离职时间排个序得到数组S2
对于每一次查询[T_start, T_end]：
step 2. 使用开始时间对S1做二分查找，找到第一个起始时间>=T_start的元素，然后
往后扫描接下来所有的符合条件的员工，得到一个计数C1
step 3. 使用结束时间对S2做二分查找，找到最后一个结束时间<=T_end的元素，然后
往前扫描所有结束时间在查询范围内，但是起始时间复）。得到一个计数C2
step 4. C1+C2就是答案
复杂度：排序(nlogn)，二分查找O(logn)，线性扫面O(M)（扫描过程中遇到的元素个数
）

y*i2014-09-04 07:09

2 楼

还是必须ex-dividend 之前？

z*a2014-09-04 07:09

3 楼

版上考古了一圈儿，各种神器也都比较了一下，看大家推荐的基本都是装在柜子下面的
，因为我们厨房设计的是准备放一个wall mounted的，所以选了与神器三代同样牌子的
两款，各项spec也都比较了一下，不过心里还是不太有底，贴上来请大家帮忙参考一下，
http://www.ventingdirect.com/cavaliere-euro-ap238-psd-36-36-sta
个人比较喜欢这款，但是不知道这个玻璃的会不会不好清洁，而且玻璃罩子感觉也有点
罩不住
http://www.ventingdirect.com/cavaliere-euro-ap238-psl-36-36-sta
因为家里的风格是比较Contemporary的，所以比较喜欢这两种外观，不过心里一直纠结
是不是还是传统的那种中式油烟机更给力，请有经验的人帮忙看看吧，谢谢啦！

M*n2014-09-04 07:09

4 楼

这个不就是meeting room II吗

s*82014-09-04 07:09

5 楼

看你是通过交易所交易，还是私下交易。

i*e2014-09-04 07:09

6 楼

我到人为装不朽钢罩的比较好。

m*f2014-09-04 07:09

7 楼

Segment tree
线段树

y*i2014-09-04 07:09

8 楼

哦，那么通过IB/sogo/etrade这些网上交易所算那种呢？

【在 s******8 的大作中提到】

: 看你是通过交易所交易，还是私下交易。

z*a2014-09-04 07:09

9 楼

是功能上有什么不同吗？还只是外观的考虑？

【在 i***e 的大作中提到】

: 我到人为装不朽钢罩的比较好。

G*O2014-09-04 07:09

10 楼

排序了扫描一遍，遇到 start 就 count++, 遇到 end 就 count--
count = 0;
x = 2005 start, count = 1
x = 2006 start, count = 2
x = 2008 end, count = 1
x = 2008 start, count = 2
x = 2010 start, count = 3
.....

s*82014-09-04 07:09

11 楼

这算交易所，不管是网上交易所，还是网下交易所，ex-dividend前买进就行。

【在 y****i 的大作中提到】

: 哦，那么通过IB/sogo/etrade这些网上交易所算那种呢？

h*o2014-09-04 07:09

12 楼

感觉玻璃罩子的不好，抽风面积小。

D*F2014-09-04 07:09

13 楼

这是经典的扫描线问题，解法不限于扫描线，但是用线段树未免牛刀宰鸡。参见
Airplanes in the sky, Meeting Room等等，就用扫描线解法就好。

i*e2014-09-04 07:09

14 楼

同意楼上说的。
不朽钢的那款，整个油烟机就是个罩子，吸风面积比玻璃的要大。

【在 z******a 的大作中提到】

: 是功能上有什么不同吗？还只是外观的考虑？

c*e2014-09-04 07:09

15 楼

int minYear = 2004;
int maxYear = 2024;
int[] yearCount = new int[maxYear - minYear + 1];
数据输入阶段
forEach (employee)
for (year = employee.start; year <= employee.end; year ++)
yearCount[year] ++;
查询阶段
int count = 0;
for (i = startYear; i <= endYear; i ++)
count += years[i];
时间复杂度是o(n)，空间复杂度是o(1)
这个问题，数量大的是员工，可以是几万，数量小的是年数，最多不过10到20年。所以
上述算法的性能很好

b*c2014-09-04 07:09

16 楼

我家是第二个，不锈钢的，型号略有不同，牌子样子一样。没考虑玻璃的，原因是清洁
和抽风面积。

下，

【在 z******a 的大作中提到】

: 版上考古了一圈儿，各种神器也都比较了一下，看大家推荐的基本都是装在柜子下面的
: ，因为我们厨房设计的是准备放一个wall mounted的，所以选了与神器三代同样牌子的
: 两款，各项spec也都比较了一下，不过心里还是不太有底，贴上来请大家帮忙参考一下，
: http://www.ventingdirect.com/cavaliere-euro-ap238-psd-36-36-sta
: 个人比较喜欢这款，但是不知道这个玻璃的会不会不好清洁，而且玻璃罩子感觉也有点
: 罩不住
: http://www.ventingdirect.com/cavaliere-euro-ap238-psl-36-36-sta
: 因为家里的风格是比较Contemporary的，所以比较喜欢这两种外观，不过心里一直纠结
: 是不是还是传统的那种中式油烟机更给力，请有经验的人帮忙看看吧，谢谢啦！

h*n2014-09-04 07:09

17 楼

最后总结时间段还是得排序，不如用楼上的办法，先排序，再++/--

【在 c*******e 的大作中提到】

: int minYear = 2004;
: int maxYear = 2024;
: int[] yearCount = new int[maxYear - minYear + 1];
: 数据输入阶段
: forEach (employee)
: for (year = employee.start; year <= employee.end; year ++)
: yearCount[year] ++;
: 查询阶段
: int count = 0;
: for (i = startYear; i <= endYear; i ++)

z*a2014-09-04 07:09

18 楼

谢谢大家的回复，准备选不锈钢罩子的了