Menu
Find best suitable time from given time interval of different users.
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
Above table show different free timesperiods available for different user, for examaple:
user1 is free in
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 is only free between this time period:
2012-07-18 21:10:47 to 2012-07-18 23:10:47
Now I want to find out one best time interval in which both user can schedule their meeting.
593
To find when both user1 and user2 are free, please try below:
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: For comparing more than 2 users,pls try below:
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 ;
Need to change m.userid in (2,4,3,5) and having count(rn)=4 according to number of users.
SQL FIDDLE HERE
84
You can use this solution to find the "best" time window in which ALL users in your criteria (let's say userids 1-5) can meet. The "best" time window is measured by the greatest amount of seconds.
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
The 4 after COUNT(DISTINCT... is just the number of users in your criteria minus one (since user's are prevented from joining onto themselves). Adjust accordingly.
What we should be returned with is the start and end time of the meeting in which all users can attend.
Given the following data:
(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);
The relative time interval positions should look like the following textual illustration (will have to sidescroll to see it all):
uid 1 <--------------------------------------------------------------------------------------...--------> <-------------------->
uid 2 <-----------------------> <-----------------------> <----> <-------------------->
uid 3 <-----------------------> <-------------------------------------------> <-------------------->
uid 4 <-----------------------> <-----------------------> <-------------------->
uid 5 <-----------------------> <-----------------------> <-------------------->
[ 1 ] [2] [ 3 ] [ 4 ]
^
We want the start and end times of this overlap
The numbers in between the brackets [ ] represent the time window in which all users' free-times overlap. We want overlap #1 since it is the longest. Overlap #1 should be 2012-07-18 1:10:00 to 2012-07-18 2:00:00, so our expected result should be:
FromDateTime | ToDateTime
----------------------------------------
2012-07-18 1:10:00 | 2012-07-18 2:00:00
The first thing we must do is figure out what the end-times are of all potential meeting windows. We do this by selecting those particular intervals in which their end-times are in between all other users' free-time intervals.
The end-times returned represent the end-times of each overlap pointed out in the textual illustration above. If there are two of the same end-times returned, we only pick one since we don't need to know anything else about that end-time other than the fact that it is the latest time that that particular meeting can go until:
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
Renders:
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 Demo
The next thing we will have to do is take the reverse of the last step and figure out all of the start-times of each potential meeting window, and join the result of this query with the result of the previous step on the condition that the start time is less than the previous step's end-time:
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
Renders:
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
The most recent FromDateTimes represent the start of each potential meeting window. We only want to pull the rows where FromDateTime is most recent per ToDateTime. We do this in the next step using GROUP BY in conjunction with the MAX() aggregate function.
SQLFiddle Demo
Next, we use GROUP BY on ToDateTime and MAX() on FromDateTime to pull only the most recent 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
Renders:
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
These are basically our potential time-windows. Now it's just a simple matter of selecting the longest one.
We use the ORDER BY / LIMIT 1 max/min selection technique since we only need one row. We order based on the seconds-difference between the end-time and start-time of each meeting, then select the one with the greatest amount of seconds (via LIMIT 1), giving us our final desired result:
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 Demo of Final Result
SQLFiddle Demo with Other Example Data
If you don't want to specify which users you want to check meeting-times for (just do it for all users in the table), you can use:
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
I created a 1D line-segment intersection algorithm in PHP utilizing a sweep line (Wikipedia). It works because datetimes can be mapped to a number-line: for example using "milliseconds since epoch".
See the implementation here: http://pastebin.com/iLwJQEF0
The algorithm outputs an array of line-segment intersections (which are also line-segments) that also have a list of all the users available for the duration. You can sort the intersections by your definition of "best" (and reverse it for descending): first by the number of available users and then by their durations. (Already implemented!)
It runs in O(n * log n), where n is the number of time-periods.
Notes:
38
I have found a hacky way to do this :
Perl has some thing called Set::IntSpan which has a intersect function(or method) that will find a range common to two intervals of numbers. The idea is to make use of it.
You can convert date time strings to timestamp(numbers) using strtotime("2012-08-27 02:02:02") in php. Once you have two pairs of timestamps, you can use the following sample perl code to find the intersection interval from which you can find the time.
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";
}
once you have the intersecting interval, you can get back the date time from timestamp (if you need) using date("Y-m-d H:i:s", $timestamp);
Here are some related links and references:
Calculate overlap between 2 ranges of numbers
Calling Perl script from PHP and passing in variables, while also using variablized perl script name
p.s. perhaps perl pros can wrap up the code into a function with 4 arguments? also, i understand this isn't the perfect answer to the question but imo the idea is cool.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
