4

I need some help with merging of overlapping intervals.

I have this table:

id  start       end
1   15:30:00    16:20:00
2   10:00:00    13:00:00
3   15:00:00    16:09:00
4   11:00:00    14:00:00
5   16:20:00    16:30:00

SQL:

CREATE TABLE `intervals` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `start` time NOT NULL,
  `end` time NOT NULL,
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

INSERT INTO `intervals` (`start`, `end`) VALUES
('15:30:00', '16:20:00'),
('10:00:00', '13:00:00'),
('15:00:00', '16:09:00'),
('11:00:00', '14:00:00'),
('16:20:00', '16:30:00');

And I want output like this:

id  start       end
2   10:00:00    14:00:00
3   15:00:00    16:30:00

Only the start and end times matter; the ID column can basically be ignored.

There is similar implementation by PHP https://stackoverflow.com/a/4347215/1085872 (until step 2) but I need to do achieve the merge with only MySQL.

Community
  • 1
  • 1
Martin Koutny
  • 41
  • 2
  • Note that some ranges that should be merged (e.g. IDs 3 and 5 in the example) don't themselves overlap. To merge them, you'll need the transitive closure of the "overlap" relationship. Calculating closures in SQL is generally hard to impossible. Why the restriction to an SQL solution? – outis Dec 07 '11 at 15:55
  • Agree, using a programming language to calculate the interval is easier. – ajreal Dec 07 '11 at 16:06
  • Found SQL solution that works - it's the top answer at http://stackoverflow.com/questions/8451925/merging-intervals-in-one-pass-in-sql – servermanfail Mar 16 '15 at 18:30

1 Answers1

-1

Try this one -

SELECT MIN(i.start) start, MAX(i.end) end FROM
  (
    SELECT @a:=@a + 1 a, t1.start, GREATEST(t1.end, t2.end) AS end
    FROM (SELECT @a := 0) t, intervals t1
    JOIN intervals t2 ON t1.id <> t2.id and t1.start >= t2.start and t1.start < t2.end
  ) p
  JOIN intervals i
     ON (i.start BETWEEN p.start AND p.end) OR (i.end BETWEEN p.start AND p.end)
  GROUP BY p.a;

+----------+----------+
| start    | end      |
+----------+----------+
| 10:00:00 | 14:00:00 |
| 15:00:00 | 16:30:00 |
+----------+----------+

The query is based on this solution - http://www.artfulsoftware.com/infotree/queries.php#807

Test it on your data.

Devart
  • 119,203
  • 23
  • 166
  • 186