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。对任何一个车次几百几千个座位，可以保证最差... 阅读全帖 |
|
