如果爱情是永恒的，就不会有失恋的痛苦。# Piebridge - 鹊桥
u*u
1 楼
请问这题C++怎么实现，很难搞的样子？
公交车管理问题
公交车站里面有若干公共汽车， 类似这样 terminal:{bus1, bus2, bus3, ...}， bus
是一个类， 有int
id, String company和一个出发时间 int time. 然后让实现几个函数 ：
- add(bus) 向一个车站里加入一辆车
- getnext() 得到下一辆出发的车
- dispatch() 让下一辆车从车站出发
- removeAll(company) 除掉车站中某一个公司的所有车。
问每个函数的时间复杂度。
Map companyToQueue，k个company，每个队列长度为L，则
- add(bus): O(logL)
- getNext(): O(k)
- dispatch(): O(k)
- removeAll(company): O(1)
follow up, 自己实现priority queue 来实现上面的每个问题。
公交车管理问题
公交车站里面有若干公共汽车， 类似这样 terminal:{bus1, bus2, bus3, ...}， bus
是一个类， 有int
id, String company和一个出发时间 int time. 然后让实现几个函数 ：
- add(bus) 向一个车站里加入一辆车
- getnext() 得到下一辆出发的车
- dispatch() 让下一辆车从车站出发
- removeAll(company) 除掉车站中某一个公司的所有车。
问每个函数的时间复杂度。
Map
- add(bus): O(logL)
- getNext(): O(k)
- dispatch(): O(k)
- removeAll(company): O(1)
follow up, 自己实现priority queue 来实现上面的每个问题。
