会议室状态用什么样的数据结构比较合理?

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

› MySQL 5.5 Community Server

› MySQL 5.6 Community Server

› Percona Configuration Wizard

› XtraBackup 搭建主从复制

Great Sites on MySQL

› Percona

› MySQL Performance Blog

› Severalnines

推荐管理工具

› Sequel Pro

› phpMyAdmin

推荐书目

› MySQL Cookbook

MySQL 相关项目

› MariaDB

› Drizzle

参考文档

› http://mysql-python.sourceforge.net/MySQLdb.html

这是一个创建于 3143 天前的主题，其中的信息可能已经有所发展或是发生改变。

会议室按时间段被用户预定后，能够快速查找某个时间段下空闲的会议室，有什么合适的结构和算法?

会议室

时间段

结构

空闲

18 条回复 • 2016-05-15 21:10:53 +08:00

kran

2016-05-13 00:17:36 +08:00 via Android

汗，挺简单的，想多了

Ouyangan

2016-05-13 01:18:25 +08:00 via Android

区间

aheadlead

2016-05-13 07:11:17 +08:00 via iPhone

你有多少个会议室？

2016-05-13 08:11:39 +08:00

关注 0-0 有高人愿意解答嘛

uxstone

2016-05-13 08:18:23 +08:00

有高手愿意解答吗？在线等 ^-^

qile1

2016-05-13 08:32:57 +08:00 via Android

用 mssql 的话，直接比对时间是不是可以，快速说不上，但是可以查询吧，会议室两个时间状态，开始时间和结束时间。这个可以查询出某个时间段是否可用，查询所以的时间段可以把所有的以订时间段取出，和 24 小时取非交集

sweetjian

2016-05-13 08:54:54 +08:00 via Android

补充一下楼上的区间法: 用一个会议室被占用链表，每个节点包括日期，开始时间，结束时间，可以方便的存储在数据库中。查询空闲时间的时候，先找出当天的占用列表，再遍历列表查询出空闲时间段，头一个节点的结束时间和下一个节点的开始时间之间就是空闲时间，另外要注意处理上下班时间。

murmur

2016-05-13 09:11:05 +08:00

你想太复杂了我跟你说做全表 scan 都用不了多少数据一个会议室按一小时预定一次全年 365 天开会才
365x24=8760 条数据全表扫描能用多少时间
何况。。你能预定一年的会议室？最多提前一两个星期都很了不起了吧。。几十条数据而已，搞那么复杂

lijsf

2016-05-13 09:26:08 +08:00

业务+算法。先考虑业务，再找合适的算法。最大预定时间是多长时间？最小预定粒度是多少？确定了之后就可以把会议室资源按可分割粒度数值化，然后预定时间就是一个数值区间，查询一般有两种，一种查可预订会议室，这种情况只需要给定区间和某个会议室的预定区间无交集即可返回 true 。另一种查询时查某个会议室的占用情况，直接查就 OK 了。

数据结构，每一个会议室对应一个 List<Long>字段，每个 long 存一个区间，高 32 位存开始时间，低 32 位存结束时间。就可以了。

annielong

2016-05-13 09:53:02 +08:00

简单粗暴，会议室 id ，开始时间，结束时间，用完数据删除，整张表也没几条

inahesun8712

2016-05-13 13:10:48 +08:00

多少会议室？几亿？如果不是就随便塞到文件里面或者数据库里面读取的时候判断下是否占用，保存的时候判断下占用就完了。

crohn

2016-05-13 14:16:32 +08:00

你想多了，直接简单粗暴 mysql 查就是了，我这边 4 个会议室用了快几个月了，也就 1500 不到，还有测试数据

byron

2016-05-13 17:30:43 +08:00

这个和家政一线保洁派单库存应该是一个道理。
计算能用的阿姨。

SlipStupig

2016-05-13 17:51:44 +08:00

一天开 100 次会，假设 365 天，假设你们公司有 100 个会议室，天天开会！那一年也就是：（ 100*365 ）* 100 行， 10 年都没多少数据....用个压缩文本都可以管理

Hihh

2016-05-13 18:31:12 +08:00

我做过这样的需求

每个会议室对应都对应一个会议室安排记录，内容是 @lijsf 说的可分割粒度，我分割为五分钟，假设会议室从早上 07:00 至晚上 23:00 这个区间可以借用，一天总共可以分为 97 位，每一位代表当前日期下这个时间节点的会议室占用情况， 0 表示空， 1 表示占用。

如果会议室最多可以借用今日之后的 60 天的话一个字段的长度就是 97*60 位。

查询占用：计算查询时间（精确到日期）在会议室安排记录中的起始位置到结束位置，如果这段区间中存在 1 就占用，否则就是空。这样的做法适用于连续借用，比如借 2016-05-13 至 2016-05-20 每天 08:00-11:00 ，效率应该还可以，也好理解。

如果是直接比较日期的交集再取非的话不直观又要考虑很多情况才能写出来而且效率还可能非常差。

samueldeng

2016-05-14 15:18:33 +08:00

资源 1->红黑树((12:00-13:00),(14:00-15:00))
资源 2->红黑树((13:00-14:00),(15:00-15:30))

至少我之前是这么存在 mem 中的。
对于单个资源而言，读与写时间复杂度均为 logN 。

数据库模型暂时没有涉及～～不过感觉蛮麻烦～～

kran

2016-05-15 15:44:07 +08:00

@Hihh 我开始想的确实是你最后说的方案

一直没有回复帖子，是想看看大家都有哪些思路，确实开阔了不少。

其实蛮关心帖子的。^ ^

Hihh

2016-05-15 21:10:53 +08:00

@kran 这种方案真的很妙