Date fields in MySQL, finding all rows that don't overlap and returning only the difference

Question

So this was one of my very first questions here, but I have a slight variation:

So I have two people whose schedules are in a database. The schedules simply record the start time, end time, and description of the various events/appointments for both users.

PersonA wants to trade appointments with PersonB. I want a MySQL query that will return all of them times that PersonB and PersonA can swap.

Originally the parameters of the query were to throw out any appointments of PersonB where there was overlap with PersonA and PersonB's appointment had to be the exact same length as the appointment PersonA wants to swap. I got some great advice on time arithmetic/geometry that helped me get the results I needed.

Now I want to change the 1-to-1 parameter so that the appointments don't have to be equal in length. So if PersonA wants to swap his Monday morning appointment (10:00 AM - 11:30 AM), the query will:

• Exclude any of PersonB's appointments that are during one of PersonA's appointments
• Include any of PersonB's appointments that are outside of PersonA's appointments
• Include the parts of PersonB's appointments that are while PersonA is free, but only show the free portion.

So if PersonA wants to swap the above appointment (again, Monday 10:00 AM - 11:30 AM), and PersonA has an appointment on Tuesday 1:00 PM to 3:00 PM and PersonB has an appointment on Tuesday from 12:00 PM to 4:00 PM, the query would return:

Possible_Swaps
==============
userID  | Start             | End             | Description
PersonB | Tuesday, 12:00 PM | Tuesday 1:00 PM | Cooking
PersonB | Tuesday,  4:00 PM | Tuesday 5:00 PM | Cooking

In addition to any other possibilities. Is this too much to expect from the database? If so, any suggestions on how to at least get those shifts that are overlapping but have the times hanging over either side so that a PHP script could deal with them?

---

per searlea's request, here's a bit more context:

I kept saying appointments but I think I really meant "jobs" as in "work shifts". PersonA and PersonB work in the same office. In vcalendar, work shifts are usually referred to as "Events" but on occasion "Appointments" and I went with the latter as it sounds less like the two Persons are going to a fair.

So PersonA has a dish-washing shift on Monday from 10:00 to 11:30 AM. PersonB is cooking on Tuesday from 12:00PM to 5:00PM. PersonA really wants to see his brother before they leave town on Monday. He'd rather get all of Monday morning off, but he'd settle for getting an hour of shift off .

So in my old model (brought up in my very first question here), I was looking for any shifts where there was no overlap and where the shifts were equal in time. But that has two problems:

1. If I need someone to cover my 2 hour shift on Tuesday and I work for 4 hours on Thursday, and Joe works for 8 hours on Thursday, I could swap two of his hours and he could leave a bit early and I can stay a bit later.

2. If I have a two hour shift, but I'd gladly trade an hour of it just to make it to the airport on time, I want to know if such and such comes in an hour earlier than me later in the week so I can take that part of his shift.

Long story short (too late), I want what is apparently known as the relative complement of PersonA's shifts to PersonB (basically any times that PersonB is working and PersonA is not, regardless of whether the shifts overlap at some other point.)

Ideally, I would get a set of results that included the bits that PersonB was working and PersonA was not (the two 1 hour shifts mentioned above), as well as the entire shift (with a special tag to indicate it is not available as a whole) so that PersonA would see that he was covering part of a shift and not get confused and think that PersonB just happened to be working two one hour shifts.

This is all starting to sound a bit complicated. Basically I want PersonB's shifts to be be blue, PersonA's shifts to be yellow, and I want the database to return all of the parts that are not green.

Answer 1

SELECT * 
  FROM schedule AS s1
WHERE
  s1.user = 'Ondra'
AND
NOT EXISTS ( 
  SELECT * FROM schedule AS s2 
  WHERE
    s2.user = 'Zizka'
    AND (
      s2.start BETWEEN s1.start AND s1.end 
      OR
      s2.end BETWEEN s1.start AND s1.end 
      OR 
      s1.start > s2.start AND s1.end < s2.end 
    )
)

This selects Ondra's events which can fit into a gap in Zizka's diary.

Edited: Originally it was an intersect, but if you want the relative complement, this is enough.

Answer 2

Let $shift_id be the id of the shift that your user wants to swap.

select swappable.shift_id, swappable.user_id, swappable.description,
    FROM_UNIXTIME(swappable.shiftstart) as start,
    FROM_UNIXTIME(swappable.shiftend) as end,
    (swappable.shiftend - swappable.shiftstart) -
        sum(coalesce(least(conflict.shiftend, swappable.shiftend) -
            greatest(conflict.shiftstart, swappable.shiftstart), 0))
        as swaptime,
    group_concat(conflict.shift_id) as conflicts,
    group_concat(concat(FROM_UNIXTIME(conflict.shiftstart), ' - ',
        FROM_UNIXTIME(conflict.shiftend))) as conflict_times
from shifts as problem
join shifts as swappable on swappable.user_id != problem.user_id
left join shifts as conflict on conflict.user_id = problem.user_id
    and conflict.shiftstart < swappable.shiftend
    and conflict.shiftend > swappable.shiftstart
where problem.shift_id = 1
group by swappable.shift_id
having swaptime > 0;

Tested with:

CREATE TABLE `shifts` (
  `shift_id` int(10) unsigned NOT NULL auto_increment,
  `user_id` varchar(20) NOT NULL,
  `shiftstart` int unsigned NOT NULL,
  `shiftend` int unsigned NOT NULL,
  `description` varchar(32) default NULL,
  PRIMARY KEY  (`shift_id`)
);

insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (1,'april', UNIX_TIMESTAMP('2009-04-04 10:00:00'),UNIX_TIMESTAMP('2009-04-04 12:00:00'),'Needs to be swapped');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (2,'bill',  UNIX_TIMESTAMP('2009-04-04 10:30:00'),UNIX_TIMESTAMP('2009-04-04 11:30:00'),'Inside today');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (3,'casey', UNIX_TIMESTAMP('2009-04-04 12:00:00'),UNIX_TIMESTAMP('2009-04-04 14:00:00'),'Immediately after today');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (4,'casey', UNIX_TIMESTAMP('2009-04-04 08:00:00'),UNIX_TIMESTAMP('2009-04-04 10:00:00'),'Immediately before today');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (5,'david', UNIX_TIMESTAMP('2009-04-04 11:00:00'),UNIX_TIMESTAMP('2009-04-04 15:00:00'),'Partly after today');

insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (6,'april', UNIX_TIMESTAMP('2009-04-05 10:00:00'),UNIX_TIMESTAMP('2009-04-05 12:00:00'),'Tommorow');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (7,'bill',  UNIX_TIMESTAMP('2009-04-05 09:00:00'),UNIX_TIMESTAMP('2009-04-05 11:00:00'),'Partly before tomorrow');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (8,'casey', UNIX_TIMESTAMP('2009-04-05 10:00:00'),UNIX_TIMESTAMP('2009-04-05 12:00:00'),'Equals tomorrow');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (9,'david', UNIX_TIMESTAMP('2009-04-05 10:30:00'),UNIX_TIMESTAMP('2009-04-05 11:30:00'),'Inside tomorrow');

insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (10,'april',UNIX_TIMESTAMP('2009-04-11 10:00:00'),UNIX_TIMESTAMP('2009-04-11 12:00:00'),'Next week');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (11,'april',UNIX_TIMESTAMP('2009-04-11 12:00:00'),UNIX_TIMESTAMP('2009-04-11 14:00:00'),'Second shift');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (12,'bill', UNIX_TIMESTAMP('2009-04-11 11:00:00'),UNIX_TIMESTAMP('2009-04-11 13:00:00'),'Overlaps two');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (13,'casey',UNIX_TIMESTAMP('2009-04-11 17:00:00'),UNIX_TIMESTAMP('2009-04-11 19:00:00'),'No conflict');

insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (14,'april',UNIX_TIMESTAMP('2009-05-04 10:00:00'),UNIX_TIMESTAMP('2009-05-04 12:00:00'),'Next month');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (15,'april',UNIX_TIMESTAMP('2009-05-04 13:00:00'),UNIX_TIMESTAMP('2009-05-04 15:00:00'),'After break');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (16,'bill', UNIX_TIMESTAMP('2009-05-04 11:00:00'),UNIX_TIMESTAMP('2009-05-04 14:00:00'),'Middle okay');

insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (17,'april',UNIX_TIMESTAMP('2010-04-04 10:00:00'),UNIX_TIMESTAMP('2010-04-04 11:00:00'),'Next year');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (18,'april',UNIX_TIMESTAMP('2010-04-04 11:30:00'),UNIX_TIMESTAMP('2010-04-04 12:00:00'),'After break');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (19,'april',UNIX_TIMESTAMP('2010-04-04 12:30:00'),UNIX_TIMESTAMP('2010-04-04 13:30:00'),'Third part');
insert  into `shifts`(`shift_id`,`user_id`,`shiftstart`,`shiftend`,`description`) values (20,'bill', UNIX_TIMESTAMP('2010-04-04 10:30:00'),UNIX_TIMESTAMP('2010-04-04 13:00:00'),'Two parts okay');

Results:

'shift_id', 'user_id', 'description',              'start',               'end',                 'swaptime', 'conflicts', 'conflict_times'
 '3',       'casey',   'Immediately after today',  '2009-04-04 12:00:00', '2009-04-04 14:00:00', '7200',       NULL,       NULL
 '4',       'casey',   'Immediately before today', '2009-04-04 08:00:00', '2009-04-04 10:00:00', '7200',       NULL,       NULL
 '5',       'david',   'Partly after today',       '2009-04-04 11:00:00', '2009-04-04 15:00:00', '10800',     '1',        '2009-04-04 10:00:00 - 2009-04-04 12:00:00'
 '7',       'bill',    'Partly before tomorrow',   '2009-04-05 09:00:00', '2009-04-05 11:00:00', '3600',      '6',        '2009-04-05 10:00:00 - 2009-04-05 12:00:00'
'13',       'casey',   'No conflict',              '2009-04-11 17:00:00', '2009-04-11 19:00:00', '7200',       NULL,       NULL
'16',       'bill',    'Middle okay',              '2009-05-04 11:00:00', '2009-05-04 14:00:00', '3600',      '15,14',    '2009-05-04 13:00:00 - 2009-05-04 15:00:00,2009-05-04 10:00:00 - 2009-05-04 12:00:00'
'20',       'bill',    'Two parts okay',           '2010-04-04 10:30:00', '2010-04-04 13:00:00', '3600',      '19,18,17', '2010-04-04 12:30:00 - 2010-04-04 13:30:00,2010-04-04 11:30:00 - 2010-04-04 12:00:00,2010-04-04 10:00:00 - 2010-04-04 11:00:00'

This shows all shifts for which any portion(s) can be swapped, including how much total time (in seconds) is swappable. The final column, conflict_times, shows the times for which the swapping user is already scheduled to work. It should be easy for the application to extract the available times from that; it's possible, but very tricky, in MySQL.

Answer 3

Task

Return all the intervals of two different users except parts where they overlap.

Table and test data

CREATE TABLE IF NOT EXISTS `shifts` (
  `id` int(11) NOT NULL auto_increment,
  `name` varchar(1) NOT NULL,
  `start` datetime NOT NULL,
  `end` datetime NOT NULL,
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=12 ;

INSERT INTO `shifts` (`id`, `name`, `start`, `end`) VALUES
(1, 'a', '2000-01-01 01:00:00', '2000-01-01 03:00:00'),
(2, 'a', '2000-01-01 06:00:00', '2000-01-01 07:30:00'),
(3, 'b', '2000-01-01 02:00:00', '2000-01-01 04:00:00'),
(4, 'b', '2000-01-01 05:00:00', '2000-01-01 07:00:00'),
(5, 'a', '2000-01-01 08:00:00', '2000-01-01 11:00:00'),
(6, 'b', '2000-01-01 09:00:00', '2000-01-01 10:00:00'),
(7, 'a', '2000-01-01 12:00:00', '2000-01-01 13:00:00'),
(8, 'b', '2000-01-01 14:00:00', '2000-01-01 14:30:00'),
(9, 'a', '2000-01-01 16:00:00', '2000-01-01 18:00:00'),
(10, 'a', '2000-01-01 19:00:00', '2000-01-01 21:00:00'),
(11, 'b', '2000-01-01 17:00:00', '2000-01-01 20:00:00');

Test results

  id name start   end
  1 a 2000-01-01 01:00:00 2000-01-01 02:00:00
  3 b 2000-01-01 03:00:00 2000-01-01 04:00:00
  4 b 2000-01-01 05:00:00 2000-01-01 06:00:00
  2 a 2000-01-01 07:00:00 2000-01-01 07:30:00
  5 a 2000-01-01 10:00:00 2000-01-01 11:00:00
  7 a 2000-01-01 12:00:00 2000-01-01 13:00:00
  8 b 2000-01-01 14:00:00 2000-01-01 14:30:00
  9 a 2000-01-01 16:00:00 2000-01-01 17:00:00
  11 b 2000-01-01 18:00:00 2000-01-01 19:00:00
  10 a 2000-01-01 20:00:00 2000-01-01 21:00:00

Solution

I used feature of MySQL called User-Defined Variables to achieve the goal with the following query:

SET @inA=0, @inB=0, @lastAstart = 0, @lastBstart = 0, @lastAend = 0, @lastBend = 0;
SELECT id,name,start,end FROM (
    SELECT 
     id,name,
     IF(name='a',
       IF(UNIX_TIMESTAMP(start) > @lastBend, start, FROM_UNIXTIME(@lastBend)),
       IF(UNIX_TIMESTAMP(start) > @lastAend, start, FROM_UNIXTIME(@lastAend))
     ) as start,
     IF(name='a',
       IF(@inB,FROM_UNIXTIME(@lastBstart),end),
       IF(@inA,FROM_UNIXTIME(@lastAstart),end)
     )  as end,
     IF(name='a',
       IF(@inB AND (@lastBstart < @lastAstart), 1, 0),
       IF(@inA AND (@lastAstart < @lastBstart), 1, 0)
     ) as fullyEnclosed,
       isStart,
       IF(name='a',@inA:=isStart,0), 
       IF(name='b',@inB:=isStart,0), 
       IF(name='a',IF(isStart,@lastAstart:=t,@lastAend:=t),0), 
       IF(name='b',IF(isStart,@lastBstart:=t,@lastBend:=t),0)
    FROM (
      (SELECT *, UNIX_TIMESTAMP(start) as t, 1 as isStart FROM `shifts` WHERE name IN ('a', 'b'))
     UNION ALL 
      (SELECT *, UNIX_TIMESTAMP(end) as t, 0 as isStart FROM `shifts` WHERE name IN ('a', 'b'))
     ORDER BY t
    ) as sae
) AS final WHERE NOT isStart AND NOT fullyEnclosed;

Basic idea is to list the table twice sorted by time so that every record appear twice. Once for the start time and then for the end time. Then I'm using user-defined variables to keep track of the state while traversing records and return only 'end time' records with start time and end time adjusted for overlapping intervals.

Assumptions

Only assumption is that no interval of person x does overlap with another interval of the same person.

Behavior

Few cases, and their results:

<  (   >   )
<  >   (   )

( < )  ( > )
( ) <  > ( )

<  (   )   >    // for this and similar cases only last part of interval is returned
       <   >

(   <  )   (   )  (  )  (   >   )  // like so
(   )                <  >   (   )

Caveats

I must have used unix timestamp since it my mysql server could not make comparison between DATETIME kept in user-defined variable and something else.

Pros & Cons

It does it's job in single pass without any joins so it should take O(N) time. It cannot retrieve all the parts of interval of person A cut out by enclosed intervals of person B. It uses MySQL specific functionality.

Answer 4

For the reference a code snipped which I used recently. It can be used to check for overlapping date ranges. It is written in Ruby on Rails, but the idea (the SQL Statement) can easily be translated to other languages)

  class Absence
    named_scope :overlaps, lambda { |start, ende| { 
      :conditions =>
          ["   absences.start_date BETWEEN :start AND :end " +
           "OR absences.end_date   BETWEEN :start AND :end " +
           "OR :start BETWEEN absences.start_date AND absences.end_date " +
           "OR :end BETWEEN absences.start_date AND absences.end_date ",
              {:start => start, :end => ende } ]
      }}
  end

As usual with named scopes this scope can be reused in combination with any other scopes.

user = User.find(...)
today = Date.today
confirmed_absences = user.absences.confirmed.overlaps(today.beginning_of_month, today.end_of_month).count