LeetCode in Racket

56. Merge Intervals

Medium

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[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: intervals = [[1,4],[4,5]]

Output: [[1,5]]

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

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Solution

(define/contract (merge intervals)
  (-> (listof (listof exact-integer?)) (listof (listof exact-integer?)))
  (if (empty? intervals)
      '()
      (let* ([sorted-intervals (sort intervals (λ (a b) (< (first a) (first b))))])
        (let merge-helper ([intervals (rest sorted-intervals)]
                          [result (list (first sorted-intervals))])
          (cond
            [(empty? intervals) result]
            [else
             (let* ([current (last result)]
                    [next (first intervals)]
                    [current-end (second current)]
                    [next-start (first next)]
                    [next-end (second next)])
               (if (<= next-start current-end)
                   ; Merge overlapping intervals
                   (merge-helper 
                    (rest intervals)
                    (append (drop-right result 1)
                           (list (list (first current) 
                                     (max current-end next-end)))))
                   ; Add non-overlapping interval
                   (merge-helper 
                    (rest intervals)
                    (append result (list next)))))])))))

This site is open source. Improve this page.