如果爱情是永恒的,就不会有失恋的痛苦。# 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 来实现上面的每个问题。