Merge and Sort Intervals

Related Projects Algorithms
1

Hi everyone,
Would someone be able to help me understand how to approach or find the solution to this question? I’d really appreciate any guidance.
Question: Given an array of intervals [startTime, endTime], merge all overlapping intervals and return a sorted array of non-overlapping intervals.
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
This is how I started but the second loop that iterates over flatIntervals isn’t giving the correct output.

  func mergeHighDefinitionIntervals(intervals: [[Int]]) -> [[Int]] {

    var result = [[Int]]()

    let flatIntervals = intervals.flatMap { $0 }

    var valid: [Int] = [flatIntervals[0]]

    for num in 2..<flatIntervals.count {

        if flatIntervals[num] > flatIntervals[num-1] {

            valid.append(flatIntervals[num])

        }

    }

    for i in stride(from: 0, to: valid.count, by: 2) {

        let pair = [valid[i], valid[i+1]]

        result.append(pair)

    }
    return result
}

print(mergeHighDefinitionIntervals(intervals: [[1, 3], [2, 6], [8, 10], [15, 18]]))
2

I'm sure that there's a more elegant way to do it (using higher-order functions), but how about this:

Basically, make an Interval into a type of its own, then add some functions to that type which check for overlaps and allows merging intervals. Then some basic iteration over the input data and merge intervals that can be merged...

Types in Swift are very useful.

//
//  main.swift
//  intervals
//
//  Created by Diggory Laycock on 25/02/2026.
//

print("Intervals: Hello, World!")

///   An interval with a start and end.
struct Interval: Comparable, CustomDebugStringConvertible {
    let start: Int
    let end: Int

    var debugDescription: String {
        "Interval(\(start) <--> \(end))"
    }

    //  Comparable
    static func <(lhs: Interval, rhs: Interval) -> Bool {
        if lhs.start == rhs.start {
            return lhs.end < rhs.end
        }
        return lhs.start < rhs.start
    }

    /// Does another interval overlap this one?
    func overlaps(another: Interval) -> Bool {
        var overlaps = true
        if (another.start < start && another.end < start) { overlaps = false }
        if (another.end > end && another.start > end) { overlaps = false }
//        print("\(self) overlaps \(another) == \(overlaps)")
        return overlaps
    }

    /// Make a new interval covering both intervals if they overlap. Otherwise do nothing
    func mergeIfPossible(another: Interval) -> Interval? {
        if !overlaps(another: another) {
            return nil
        }
        return Interval(start: min(self.start, another.start), end: max(self.end, another.end))
    }

}

let sampleData = [
    Interval(start: 30, end: 33),
    Interval(start: 27, end: 30),
    Interval(start: 1, end: 3),
    Interval(start: 2, end: 6),
    Interval(start: 8, end: 10),
    Interval(start: 15, end: 18),
    Interval(start: 20, end: 25),
    Interval(start: 21, end: 23),
    Interval(start: 22, end: 26),
]

let sortedIntervals = sampleData.sorted()
print("sortedIntervals:")
print(sortedIntervals)

//  Merge overlapping intervals

var unmergedIntervals = sortedIntervals
var mergedIntervals = [Interval]()

var done = false
while !done {
    if unmergedIntervals.count == 0 {
        print("no more unmerged to process")
        done = true
        continue
    }
    let candidate = unmergedIntervals.first!
    if let lastMerged = mergedIntervals.last {
        if let mergeResult = lastMerged.mergeIfPossible(another: candidate) {
            //  Overlapping, can be merged
//            print("We can merge \(candidate) and \(lastMerged) to become: \(mergeResult)")
            mergedIntervals.removeLast()
            mergedIntervals.append(mergeResult)
        } else {
            //  Not overlapping
            mergedIntervals.append(candidate)
        }
    } else {
        //  This is the first to merge
        mergedIntervals.append(candidate)
    }
    //  We are done with this element
    unmergedIntervals.removeFirst()
}

print("Merged:")
print(mergedIntervals)

Outputs:

Intervals: Hello, World!
sortedIntervals:
[Interval(1 <--> 3), Interval(2 <--> 6), Interval(8 <--> 10), Interval(15 <--> 18), Interval(20 <--> 25), Interval(21 <--> 23), Interval(22 <--> 26), Interval(27 <--> 30), Interval(30 <--> 33)]
no more unmerged to process
Merged:
[Interval(1 <--> 6), Interval(8 <--> 10), Interval(15 <--> 18), Interval(20 <--> 26), Interval(27 <--> 33)]
Program ended with exit code: 0
1 Like
3

Looks like the Advent of Code 2025 Day 5 part 2 puzzle.

I used ClosedRange to describe the intervals, instead of array of array of integers.

First I sorted the input ranges so that they are in natural order of lower range by upper range.

Then I created an empty set of result ranges and started to handle the input ranges from the sorted array. The first input range can be just added to the result set.

If the currently handled range from the (sorted ranges) is already contained in the result set of ranges, that input range is skipped.

If the currently handled range from the input overlaps with a range in the result set, I created a new range that combines the two overlapping ranges and replaced the range in result set with this new "wider" range. Thus, when handling the input range 2...6 the range 1...3 already in the result set is replaced with a new range 1...6.

And obviously, if the currently handled input range is not contained or overlapping with any range in the result set of ranges, it is added to the result set as-is.

2 Likes
4

The standard library has this functionality built-in, in the form of the (little-known, I think) RangeSet type, provided you're OK with switching from arrays to half-open Range values.

With your example:

var intervals = RangeSet<Int>()
// These insertions don't have to be in order.
// RangeSet will keep them sorted.
intervals.insert(contentsOf: 1..<4)
intervals.insert(contentsOf: 2..<7)
intervals.insert(contentsOf: 8..<11)
intervals.insert(contentsOf: 15..<19)

// The `.ranges` property is a collection of the consolidated ranges:
print(intervals.ranges)
// → [Range(1..<7), Range(8..<11), Range(15..<19)]

// Convert to an array of arrays in your desired form:
let intervalArray = intervals.ranges.map { [$0.lowerBound, $0.upperBound-1] }
print(intervalArray)
// → [[1, 6], [8, 10], [15, 18]]
6 Likes
5

Didn't know about RangeSet! Using it drops out 28 lines of code from my AoC Day 5 part 2 down to total of nine lines of code, as well as drops the execution time from 0.0025 to 0.0011 secs. Thank you!

1 Like