5

从不同用户的给定时间间隔中找到最合适的时间。

Rows: 5
fid  userid  FromDateTime           ToDateTime          flag
62   1   2012-07-18 01:48:20    2012-07-18 02:55:20     1
63   1   2012-07-18 10:30:46    2012-07-18 12:54:46     1
64   1   2012-07-18 18:50:24    2012-07-18 20:35:24     1
67   1   2012-07-18 15:03:36    2012-07-18 16:03:36     1
68   2   2012-07-18 21:10:47    2012-07-18 23:10:47     1

上表显示了不同用户可用的不同空闲时间段，例如：

user1是免费的

2012-07-18 01:48:20   to   2012-07-18 02:55:20 , 
2012-07-18 10:30:46   to   2012-07-18 12:54:46 
......

user 2仅在此时间段之间免费：

2012-07-18 21:10:47   to   2012-07-18 23:10:47

现在我想找出两个用户都可以安排会议的最佳时间间隔。

4

5 回答 5

8

要查找 user1 和 user2 何时空闲，请尝试以下操作：

select 
a.datetime_start as user1start,a.datetime_end as user1end,
b.datetime_start as user2start,b.datetime_end as user2end ,
case when a.datetime_start > b.datetime_start then a.datetime_start 
   else b.datetime_start end as avail_start,
case when a.datetime_end>b.datetime_end then b.datetime_end 
   else a.datetime_end end as avail_end
from users a inner join users b on
a.datetime_start<=b.datetime_end and a.datetime_end>=b.datetime_start     
and  a.userid={user1} and b.userid={user2}

SQL 小提琴在这里。

已编辑：要比较 2 个以上的用户，请尝试以下操作：

select max(datetime_start) as avail_start,min(datetime_end) as avail_end
from(
        select *,
        @rn := CASE WHEN @prev_start <=datetime_end and @prev_end >=datetime_start THEN @rn ELSE @rn+1 END AS rn,
        @prev_start := datetime_start,
        @prev_end := datetime_end 
        from(
          select * from users2 m
          where exists ( select null 
                          from users2 o 
                           where o.datetime_start <= m.datetime_end and o.datetime_end >= m.datetime_start
                           and o.id <> m.id 
                        ) 
             and m.userid in (2,4,3,5)
           order by m.datetime_start) t,
           (SELECT @prev_start := -1, @rn := 1, @prev_end=-1) AS vars 
) c 
group by rn 
having count(rn)=4 ;

需要根据用户数量m.userid in (2,4,3,5)进行更改。having count(rn)=4

SQL 小提琴在这里

于 2012-08-15T08:44:58.850 回答
7

您可以使用此解决方案找到符合您的条件（例如1-5）的所有userids用户可以满足的“最佳”时间窗口。“最佳”时间窗口是通过最大的秒数来衡量的。

SELECT   MAX(b.FromDateTime) FromDateTime, 
         a.ToDateTime
FROM     (
         SELECT   DISTINCT a.ToDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid     <> b.userid
                       AND a.userid     IN (1,2,3,4,5)
                       AND b.userid     IN (1,2,3,4,5)
                       AND a.ToDateTime >  b.FromDateTime 
                       AND a.ToDateTime <= b.ToDateTime
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime
         HAVING   COUNT(DISTINCT b.userid) = 4
         ) a
JOIN     (
         SELECT   DISTINCT a.FromDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid       <> b.userid
                       AND a.userid       IN (1,2,3,4,5)
                       AND b.userid       IN (1,2,3,4,5)
                       AND a.FromDateTime >= b.FromDateTime 
                       AND a.FromDateTime <  b.ToDateTime
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime
         HAVING   COUNT(DISTINCT b.userid) = 4
         ) b ON b.FromDateTime < a.ToDateTime
GROUP BY a.ToDateTime
ORDER BY TIMESTAMPDIFF(SECOND, MAX(b.FromDateTime), a.ToDateTime) DESC
LIMIT    1

4后面只是您的COUNT(DISTINCT...标准中的用户数减一（因为用户被阻止加入自己）。相应调整。

我们应该返回的是所有用户都可以参加的会议的开始和结束时间。

查询细分

给定以下数据：

(62, 1, '2012-07-18 00:00:00', '2012-07-18 12:00:00', 1),

(63, 2, '2012-07-18 00:00:00', '2012-07-18 02:00:00', 1),
(64, 2, '2012-07-18 03:00:00', '2012-07-18 05:00:00', 1),
(65, 2, '2012-07-18 05:30:00', '2012-07-18 06:00:00', 1),

(66, 3, '2012-07-18 00:30:00', '2012-07-18 02:30:00', 1),
(67, 3, '2012-07-18 03:10:00', '2012-07-18 07:30:00', 1),

(68, 4, '2012-07-18 01:10:00', '2012-07-18 03:20:00', 1),
(69, 4, '2012-07-18 03:50:00', '2012-07-18 06:00:00', 1),

(70, 5, '2012-07-18 01:10:00', '2012-07-18 03:20:00', 1),
(71, 5, '2012-07-18 04:30:00', '2012-07-18 07:10:00', 1),


(72, 1, '2012-07-18 13:00:00', '2012-07-18 14:00:00', 1),
(73, 2, '2012-07-18 13:30:00', '2012-07-18 14:30:00', 1),
(74, 3, '2012-07-18 14:00:00', '2012-07-18 15:00:00', 1),
(75, 4, '2012-07-18 14:30:00', '2012-07-18 15:30:00', 1),
(76, 5, '2012-07-18 18:00:00', '2012-07-18 19:00:00', 1);

相对时间间隔位置应如下图所示（必须横向滚动才能看到全部内容）：

uid 1   <--------------------------------------------------------------------------------------...-------->      <-------------------->
uid 2   <----------------------->          <----------------------->    <---->                                          <-------------------->
uid 3       <----------------------->       <------------------------------------------->                                       <-------------------->
uid 4                 <----------------------->      <----------------------->                                                         <-------------------->
uid 5                 <----------------------->              <----------------------->                                                                                              <-------------------->
                      [    1    ]           [2]              [  3  ]    [ 4  ]
                           ^
       We want the start and end times of this overlap

括号中的数字[ ]代表所有用户空闲时间重叠的时间窗口。我们想要重叠#1，因为它是最长的。重叠 #1 应该是2012-07-18 1:10:00to 2012-07-18 2:00:00，所以我们的预期结果应该是：

FromDateTime       | ToDateTime
----------------------------------------
2012-07-18 1:10:00 | 2012-07-18 2:00:00

步骤1：

我们必须做的第一件事是弄清楚所有潜在会议窗口的结束时间。我们通过选择其结束时间在所有其他用户的空闲时间间隔之间的特定间隔来做到这一点。

返回的结束时间表示上面文字插图中指出的每个重叠的结束时间。如果返回了两个相同的结束时间，我们只选择一个，因为我们不需要知道关于该结束时间的任何其他信息，除了这是该特定会议可以进行到的最晚时间这一事实：

SELECT   DISTINCT a.ToDateTime
FROM     tbl a
JOIN     tbl b ON a.userid     <> b.userid
              AND a.userid     IN (1,2,3,4,5)
              AND b.userid     IN (1,2,3,4,5)
              AND a.ToDateTime >  b.FromDateTime 
              AND a.ToDateTime <= b.ToDateTime
GROUP BY a.userid,
         a.FromDateTime,
         a.ToDateTime
HAVING   COUNT(DISTINCT b.userid) = 4

渲染：

TODATETIME
-------------------
2012-07-18 02:00:00
2012-07-18 05:00:00
2012-07-18 06:00:00
2012-07-18 03:20:00

SQLFiddle 演示

第2步：

接下来我们要做的是与上一步相反，找出每个潜在会议窗口的所有开始时间，并将此查询的结果与上一步的结果连接起来，条件是开始时间小于上一步的结束时间：

SELECT   b.FromDateTime,
         a.ToDateTime
FROM     (
         SELECT   DISTINCT a.ToDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid     <> b.userid
                       AND a.userid     IN (1,2,3,4,5)
                       AND b.userid     IN (1,2,3,4,5)
                       AND a.ToDateTime >  b.FromDateTime 
                       AND a.ToDateTime <= b.ToDateTime
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime
         HAVING   COUNT(DISTINCT b.userid) = 4
         ) a
JOIN     (
         SELECT   DISTINCT a.FromDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid       <> b.userid
                       AND a.userid       IN (1,2,3,4,5)
                       AND b.userid       IN (1,2,3,4,5)
                       AND a.FromDateTime >= b.FromDateTime 
                       AND a.FromDateTime <  b.ToDateTime
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime
         HAVING   COUNT(DISTINCT b.userid) = 4
         ) b ON b.FromDateTime < a.ToDateTime
ORDER BY a.ToDateTime, b.FromDateTime --Ordered for display purposes

渲染：

TODATETIME          | FROMDATETIME        
------------------------------------------
2012-07-18 02:00:00 | 2012-07-18 01:10:00  <-- Most recent FromDateTime
2012-07-18 03:20:00 | 2012-07-18 01:10:00 
2012-07-18 03:20:00 | 2012-07-18 03:10:00  <-- Most recent FromDateTime
2012-07-18 05:00:00 | 2012-07-18 01:10:00 
2012-07-18 05:00:00 | 2012-07-18 03:10:00 
2012-07-18 05:00:00 | 2012-07-18 04:30:00  <-- Most recent FromDateTime 
2012-07-18 06:00:00 | 2012-07-18 01:10:00 
2012-07-18 06:00:00 | 2012-07-18 03:10:00 
2012-07-18 06:00:00 | 2012-07-18 04:30:00 
2012-07-18 06:00:00 | 2012-07-18 05:30:00  <-- Most recent FromDateTime

最近FromDateTimes的代表每个潜在会议窗口的开始。我们只想拉取FromDateTime最近的每行ToDateTime。我们在下一步GROUP BY中与MAX()聚合函数一起使用。

SQLFiddle 演示

第 3 步：

接下来，我们使用GROUP BYonToDateTime和MAX()onFromDateTime仅拉取最新的FromDateTimes：

SELECT   MAX(b.FromDateTime) FromDateTime, 
         a.ToDateTime
FROM     (
         SELECT   DISTINCT a.ToDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid     <> b.userid
                       AND a.userid     IN (1,2,3,4,5)
                       AND b.userid     IN (1,2,3,4,5)
                       AND a.ToDateTime >  b.FromDateTime 
                       AND a.ToDateTime <= b.ToDateTime
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime
         HAVING   COUNT(DISTINCT b.userid) = 4
         ) a
JOIN     (
         SELECT   DISTINCT a.FromDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid       <> b.userid
                       AND a.userid       IN (1,2,3,4,5)
                       AND b.userid       IN (1,2,3,4,5)
                       AND a.FromDateTime >= b.FromDateTime 
                       AND a.FromDateTime <  b.ToDateTime
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime
         HAVING   COUNT(DISTINCT b.userid) = 4
         ) b ON b.FromDateTime < a.ToDateTime
GROUP BY a.ToDateTime

渲染：

FROMDATETIME        | TODATETIME
-----------------------------------------
2012-07-18 01:10:00 | 2012-07-18 02:00:00
2012-07-18 03:10:00 | 2012-07-18 03:20:00
2012-07-18 04:30:00 | 2012-07-18 05:00:00
2012-07-18 05:30:00 | 2012-07-18 06:00:00

这些基本上是我们潜在的时间窗口。现在只需选择最长的一个即可。

第4步：

我们使用ORDER BY/ LIMIT 1max/min 选择技术，因为我们只需要一行。我们根据每次会议的结束时间和开始时间之间的秒差进行排序，然后选择秒数最多的一个（通过LIMIT 1），得到我们最终想要的结果：

SELECT   MAX(b.FromDateTime) FromDateTime, 
         a.ToDateTime
FROM     (
         SELECT   DISTINCT a.ToDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid     <> b.userid
                       AND a.userid     IN (1,2,3,4,5)
                       AND b.userid     IN (1,2,3,4,5)
                       AND a.ToDateTime >  b.FromDateTime 
                       AND a.ToDateTime <= b.ToDateTime
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime
         HAVING   COUNT(DISTINCT b.userid) = 4
         ) a
JOIN     (
         SELECT   DISTINCT a.FromDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid       <> b.userid
                       AND a.userid       IN (1,2,3,4,5)
                       AND b.userid       IN (1,2,3,4,5)
                       AND a.FromDateTime >= b.FromDateTime 
                       AND a.FromDateTime <  b.ToDateTime
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime
         HAVING   COUNT(DISTINCT b.userid) = 4
         ) b ON b.FromDateTime < a.ToDateTime
GROUP BY a.ToDateTime
ORDER BY TIMESTAMPDIFF(SECOND, MAX(b.FromDateTime), a.ToDateTime) DESC
LIMIT    1

最终结果的 SQLFiddle 演示

带有其他示例数据的 SQLFiddle 演示

获取表中所有用户之间的会议时间（无条件）：

如果您不想指定要检查哪些用户的会议时间（只需为表中的所有用户执行此操作），您可以使用：

SELECT   MAX(b.FromDateTime) FromDateTime, 
         a.ToDateTime
FROM     (
         SELECT     DISTINCT a.ToDateTime
         FROM       tbl a
         JOIN       tbl b ON a.userid     <> b.userid
                         AND a.ToDateTime >  b.FromDateTime 
                         AND a.ToDateTime <= b.ToDateTime
         CROSS JOIN (SELECT COUNT(DISTINCT userid) totalusers FROM tbl) c
         GROUP BY   a.userid,
                    a.FromDateTime,
                    a.ToDateTime,
                    c.totalusers
         HAVING     COUNT(DISTINCT b.userid) = c.totalusers-1
         ) a
JOIN     (
         SELECT   DISTINCT a.FromDateTime
         FROM     tbl a
         JOIN     tbl b ON a.userid       <> b.userid
                       AND a.FromDateTime >= b.FromDateTime 
                       AND a.FromDateTime <  b.ToDateTime
         CROSS JOIN (SELECT COUNT(DISTINCT userid) totalusers FROM tbl) c
         GROUP BY a.userid,
                  a.FromDateTime,
                  a.ToDateTime,
                  c.totalusers
         HAVING   COUNT(DISTINCT b.userid) = c.totalusers-1
         ) b ON b.FromDateTime < a.ToDateTime
GROUP BY a.ToDateTime
ORDER BY TIMESTAMPDIFF(SECOND, MAX(b.FromDateTime), a.ToDateTime) DESC
LIMIT    1
于 2012-08-26T11:58:46.583 回答
2

我使用扫描线（维基百科）在 PHP 中创建了一个一维线段相交算法。它之所以有效，是因为日期时间可以映射到数字线：例如使用“自纪元以来的毫秒数”。

请参阅此处的实现：http: //pastebin.com/iLwJQEF0

该算法输出一组线段交叉点（也是线段），其中还包含在该持续时间内可用的所有用户的列表。您可以按照“最佳”的定义对交叉点进行排序（并将其反转为降序）：首先按可用用户的数量，然后按他们的持续时间。（已经实施！）

它在 中运行O(n * log n)，其中n是时间段数。

笔记：

  • 如果您不想搞乱日期时间到毫秒的转换，可以替换减法和大于/小于运算符。（我给你留下了一些评论。）
  • 注意在同一位置开始/结束的线段很重要：
    • 扫描线必须在相同值的起点之前遇到终点。
    • 另请注意，当两个线段以相同的值结束时，它不会产生无关的结果。
  • 我确信这可以在数据库引擎中重新实现（如果您认为值得的话）。许多数据库供应商都有几何扩展。
于 2012-08-27T02:20:28.157 回答
1

我找到了一个hacky方法来做到这一点：

Perl 有一些叫做的东西Set::IntSpan，它有一个intersect函数（或方法），可以找到两个数字间隔的公共范围。这个想法是利用它。

您可以使用 php.ini 将日期时间字符串转换为时间戳（数字）strtotime("2012-08-27 02:02:02")。一旦你有两对时间戳，你可以使用下面的示例 perl 代码来找到你可以从中找到时间的交集间隔。

use Set::IntSpan;

my $r1 = Set::IntSpan->new([ 5 .. 15 ]);
my $r2 = Set::IntSpan->new([ 2 .. 20 ]);

my $i = $r1->intersect($r2);

if ( !$i->empty and ( $i->max - $i->min ) >= 5 ) # criteria
{
print "hit\n"; # $i->max, $i->min are the timestamps you need
}
else
{
print "miss\n";
}

一旦有了相交间隔，就可以使用时间戳（如果需要）取回日期时间date("Y-m-d H:i:s", $timestamp);

以下是一些相关链接和参考资料：

计算2个数字范围之间的重叠

从 PHP 调用 Perl 脚本并传入变量，同时还使用可变的 perl 脚本名称

ps也许perl专业人士可以将代码包装成一个有4个参数的函数？另外，我知道这不是问题的完美答案，但 imo 这个想法很酷。

于 2012-08-26T20:39:19.317 回答
0

使用小提琴中的 sel 模式（10x sel）......

最简单的方法也是：

SELECT
    MAX(GREATEST(u1.datetime_start, u2.datetime_start)) AS MeetingStart,
    MIN(LEAST(u1.datetime_end, u2.datetime_end)) AS MeetingEnd
FROM users2 u1
INNER JOIN users2 u2
    ON (u1.datetime_end >= u2.datetime_start AND u1.datetime_start <= u2.datetime_end)
    AND u2.userid != u1.userid
    AND u2.userid IN (3,4,5)
WHERE u1.userid=2
GROUP BY u1.id
HAVING COUNT(DISTINCT u2.userid) = 3 AND MeetingStart < MeetingEnd

根据你的情况改变：

在我的示例中，我们有 4 个参与者。n=4，参与者（2,3,4,5）

IN (3,4,5) --> 参加会议的最后 n-1 个 id

WHERE u1.userid=2 --> 会议第一个参与者的 id

有 COUNT(DISTINCT u2.userid) = 3 --> n - 1

可以在sqlfiddle上测试

于 2012-08-26T22:24:53.630 回答