Swift O(n log n) solution with inline comments


  • 0
    M

    Brief Swift implementation with step by step comments.

    class Solution {
        func merge(_ intervals: [Interval]) -> [Interval] {
            var result: [Interval] = []
            // sort the intervals by start so we can test for overlaps sequentially
            let intervalsSorted = intervals.sorted(by: {$0.start < $1.start})
            
            // iterate the intervals
            for interval in intervalsSorted {
                // does the current interval overlap the last
                if !result.isEmpty && interval.start <= result.last!.end {
                    // there is overlap, rewrite the last interval with the
                    // higher end value, the start value must be <= current
                    // due to the prior sort
                    result.last!.end = max(result.last!.end, interval.end)
                } else {
                    // no overlap (or no last), append current interval
                    result.append(interval)
                }
            }
            
            return result
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.