T********i 发帖数: 2416 | 2 假定一条线路从始至终一共m个区段,n个座位。
初始化:
m个array:[0,n-1] with name SegMap
memset to 0
输入:
任何时候有人购买了区段a,b。a <= b && 0 <= a <= m - 1 && 0 <= b <= m-1。
初始化array t[0, n - 1] = sum of SeqMap[from a to b]
Search array t from 0 to n-1, find the first index with the minimum value V。
If the minimum V > 0 then repeat the algo on "subsegments with which the
seat has been taken"。
具体原则:
座位编号,每次都从第编号座位开始分配。
每次分配一个需要换座最少方案
注意,换座不可避免的。但是可证明这是实时算法中最优化的。
时间复杂度,空间复杂度:
O(m * n)
注意,本算法只能单线程实现。
但是可以scale out。对任何一个车次几百几千个座位,可以保证最差... 阅读全帖 |
|