Wednesday, April 09, 2014

merge ranges

Merges list of ranges.

(1,3), (4,6) => (1,6)
(1,3), (2,6) => (1,6)
(1,6), (2,3) => (1,6)
(1,3), (8,9) => (1,3), (8,9)
(1,3), (4,6), (8,9) => (1,6), (8,9)
(4,6), (1,2) => throw

range
    int start
    int end

ranges merge(ranges):
    if ranges == null:
        throw
    merged = new
    if ranges.count() == 0:
        return merged
    start, end = 0
    first = true
    for range in ranges:
        if first:
            first = false
            start = range.start
            end = range.end
            continue
        if range.start < start:
            throw new ex("ranges not sorted asc by start value.")
        if range.start +1 <= end:
            end = max(end, range.end)
        else
            merged.add(new range(start, end))
            start = range.start
            end = range.end
    merged.add(new range(start, end))
    return merged


[Hat tip to SD]

No comments:

Post a Comment