merge-intervals

This is a leetcode posted to the Rands Leadership Slack

Problem Statement

Given an array of intervals where intervals[i] = [start[i], end[i]], merge all overlapping intervals, and return the shortest array possible representing the, non-overlapping intervals that cover all the intervals in the input.

Example 1

Input:

intervls

1	3
8	10
2	6
15	18

Output:

1	6
8	10
15	18

Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input:

1	4
4	5

Output:

1

5

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start[i] <= end[i] <= 10^4

Brainstorming

Well first of all, the second half of the question is a red herring. If you've merged all overlapping intervals, then what remains is the smallest set of non-overlapping intervals that covers all

So really this is just about merging intervals which is easy enough. First sort by start, then move through the list one at a time merging intervals until your each a gap between the current end and next next start

Implementation

In Python

def merge_intervals(intervals):
    sorted_by_start = iter(sorted(intervals, key=lambda t: t[0]))
    current_start, current_end = next(sorted_by_start)

    for next_start, next_end in sorted_by_start:
        if current_end < next_start:
            yield (current_start, current_end)
            current_start, current_end = next_start, next_end
        elif current_end < next_end:
            current_end = next_end

    yield (current_start, current_end)

return list(merge_intervals(intervals))

Run it on example-1

1	6
8	10
15	18

Run it on example-2

1

5

It works!

What about the edge case where an interval is fully contained [1,7] [2, 4]?

1

7

In Emacs Lisp

(require 'dash)
(cl-loop with sorted-intervals = (--sort (< (car it) (car other)) intervals)
         with (current-start current-end) = (car sorted-intervals)
         for (next-start next-end) in (cdr sorted-intervals)
         if (< current-end next-start)
         collect `(,current-start ,current-end) into res
         and do (setq current-start next-start)
         and do (setq current-end next-end)
         else if (< current-end next-end)
         do (setq current-end next-end)
         finally return (append res `((,current-start ,current-end))))

1	6
8	10
15	18

Run it on example-2

1

5

and now that edge case

1

7

Sweet! I love that loop facility macro, so fun!