抛砖引玉, 考虑不周到的地方请大家提意见,在zhihu上也提问了 问题描述这样, 一列火车有m个座位,n个区间段,现在有x个人上车,x< m*n, 当第i (a-b)个人上车时,必须能够找到一个最优的座位(尽量利用已售过区间的座位,让车票售出量最多) ,写出查询速度,订票速度(包括取消票) 题中可知 m >> n

站点通过查询将其转化为一个自然数序列,方便计算 算法1 现在看来效率比较低 我开始是这样设计,仿照内存分配算法, 暂且不考虑字节优化 emptyRange{ short number short size nextRange } 每个座位是个SkipList

查询 火车票是否有座就遍历链表 找到 node.number <= a && node.number+size >=b 就认为有座

订票 这个要求最优解 ,找产生碎片最小的情况,也就是说 size - (b-a) 是最小的,然后修改该空白node,如果分成两个区间就增加一个node

取消 找到对应节点,把该空白区域加入到列表里,需要合并的合并

匆匆想的,有些细节还没考虑清楚,我是想大家一起讨论下, 看看有没有更好的算法

Btw, 从关系数据库 -> NoSql ->? 下一个是什么呢?我想有没有可能是自定义数据结构服务器呢? Redis算是一个数据结构服务器,目前不太清楚设计好一种算法后,是否很容易整合进去。或者将来是否有一种开放的数据结构服务器?数据结构服务器上的数据者定期存储或者同步到数据库中。

刚才查了下 最多停靠站的火车是62个,车厢最长20节左右,客车座位数一节我们可以照200算(无坐也算) 一个座位最坏情况下 是n/2长链表,所有座位都是这样,嗯,总共一列车最坏可以用到20*200* (2+2+4) * (62/2 * 1.33)大概是 1289600 1.2M个字节 8G可用内存 可以存储 8*1024*1024*1024/1289600 = 6661辆 没有查到客列总数,想来不会超过一万辆 照10000算 12天 20台电脑也够了

算法 2 受无锋之刃 算法1 启发

为所有区段生成一个二维数组,排序如下

A B C D

B C D

C D

D

每个节点存储该区间车票数量和车票

查询 找到起始站点,再到其中找终点,从该点向下的节点都是有票得,然后再到起始站点-1 向下找 总共时间复杂度为O(i)

订票 同查询,找到该区段,如果没有,就找终点+1, 然后,起点-1, 终点+2,交错找下去,找到第一张票,复杂度O(i*(n-i)),找到之后将该区间分解,除去订票区间,然后将剩余的挂到相应的站点下

取消 遍历,找以该票起始点为终点的空白段,和以该票终点为起始点的空白段,如果找到就合并,找不到就直接加入到以该票起始和终点统计的区段 还没想好,如果遍历需要花O(m)