菜鸟也来问一个关于油烟机选择的问题# Living
v*y
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)(扫描过程中遇到的元素个数
)
公司里有好多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的元素,然后
往前扫描所有结束时间在查询范围内,但是起始时间
step 4. C1+C2就是答案
复杂度:排序(nlogn),二分查找O(logn),线性扫面O(M)(扫描过程中遇到的元素个数
)