v******y
发帖数: 23 | 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)（扫描过程中遇到的元素个数
） | M****n
发帖数: 109 | | m*f
发帖数: 3078 | | G**O
发帖数: 147 | 4 排序了扫描一遍，遇到 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
..... | D**F
发帖数: 76 | 5 这是经典的扫描线问题，解法不限于扫描线，但是用线段树未免牛刀宰鸡。参见
Airplanes in the sky, Meeting Room等等，就用扫描线解法就好。 | c*******e
发帖数: 373 | 6 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年。所以
上述算法的性能很好 | h*********n
发帖数: 11319 | 7 最后总结时间段还是得排序，不如用楼上的办法，先排序，再++/--
【在 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 ++)
|
|
