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 FIDDLE HERE.

EDITED：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

4afterは、COUNT(DISTINCT...基準内のユーザー数から 1 を引いたものです (ユーザーは自分自身に参加できないため)。それに応じて調整します。

返されるのは、すべてのユーザーが参加できる会議の開始時間と終了時間です。

クエリの内訳

次のデータがあるとします。

(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:00to2012-07-18 2:00:00である必要があるため、期待される結果は次のようになります。

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

ステップ1：

最初に行う必要があるのは、すべての潜在的な会議ウィンドウの終了時刻を把握することです。これは、終了時間が他のすべてのユーザーの自由時間間隔の間にある特定の間隔を選択することによって行われます。

返される終了時間は、上のテキストの図で指摘されている各オーバーラップの終了時間を表します。同じ終了時刻が 2 つ返された場合は、その特定の会議が終了するまでの最終時刻であるという事実以外に、その終了時刻について他に何も知る必要がないため、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()onを使用してFromDateTime、最新のものだけをプルします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:

必要な行は 1 行だけなので、 ORDER BY/ max/min 選択手法を使用します。LIMIT 1各ミーティングの終了時間と開始時間の秒差に基づいて順序付けを行い、( を介して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 で、スイープ ラインを使用して 1D 線分交差アルゴリズムを作成しました ( Wikipedia )。たとえば、「エポックからのミリ秒」を使用して、日時を数直線にマップできるため、機能します。

ここで実装を参照してください: http://pastebin.com/iLwJQEF0

このアルゴリズムは、期間中に利用可能なすべてのユーザーのリストも含む、線分の交点 (線分でもあります) の配列を出力します。「最良」の定義によって交差を並べ替えることができます (降順では逆にします)。最初に利用可能なユーザーの数で、次にその期間で並べ替えます。（実装済み！）

で実行されO(n * log n)ますn。 は期間の数です。

ノート：

  • 日時からミリ秒への変換をいじりたくない場合は、減算演算子と大なり/小なり演算子を置き換えることができます。（私はあなたのためにいくつかのコメントを残しました。）
  • 同じ場所で開始/終了する線分に注意することが重要です。
    • スイープ ラインは、同じ値の開始点の前に終点に遭遇する必要があります。
    • また、2 つの線分が同じ値で終了しても、無関係な結果が作成されないことに注意してください。
  • これは、データベース エンジン内で再実装できると確信しています (価値があると思われる場合)。多くのデータベース ベンダーは、ジオメトリック エクステンションを持っています。
于 2012-08-27T02:20:28.157 に答える
1

これを行うハックな方法を見つけました：

Perl には、数値の 2 つの間隔に共通する範囲を見つける関数 (またはメソッド) をSet::IntSpan持つものがあります。intersectそれを活かすという発想です。

PHPを使用して、日時文字列をタイムスタンプ（数字）に変換できますstrtotime("2012-08-27 02:02:02")。2 組のタイムスタンプを取得したら、次のサンプル 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つの引数を持つ関数にまとめることができますか? また、これが質問に対する完璧な答えではないことは理解していますが、アイデアはクールです。

于 2012-08-26T20:39:19.317 に答える
0

フィドル（10x sel）からの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

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

sqlfiddleでテスト可能

于 2012-08-26T22:24:53.630 に答える