kinda a lazyweb question, but i couldn’t find a very good kotlin solution. what’s the best way to fi...

# announcements

[no]

kinda a lazyweb question, but i couldn’t find a very good kotlin solution.
what’s the best way to find the union of a set of intervals.
for example:
given: [1,3], [2,5], [8,9]
result is: [1,5], [8,9]

[no]

here’s a java stackoverflow version: https://codereview.stackexchange.com/questions/126906/finding-the-total-time-elapsed-in-the-union-of-time-intervals

[Jakub Pi]

fun unionOfIntervals(intervals : List<Pair<Int,Int>>) : List<Pair<Int,Int>> {
    fun merge(l : Pair<Int, Int>, r : Pair<Int, Int>) : Pair<Int, Int> = Pair(min(l.first, r.first), max(l.second, r.second))
    val sortedIntervals = intervals.sortedBy { it.first }
    return sortedIntervals.fold(mutableListOf<Pair<Int,Int>>()) { acc, pair ->
        when {
            acc.isEmpty() -> mutableListOf(pair)
            acc.last().second >= pair.first -> acc.apply { this[acc.size-1] = merge(acc.last(), pair)}
            else -> acc.apply { add(pair) }
        }
    }
}

[no]

ah thank you! i actually phrased the question wrong, but that’s exactly what i asked for 🙂
i just need the totalTime 🙂

[no]

very nice code though!

[Jakub Pi]

Just add

.sumBy { it.second - it.first }

to the call :)

[no]

very nice

[nkiesel]

4 is not in your result, is it? So result should really be [1,3],[5],[8,9]]. And assuming we are talking about closed intervals here, you need `.sumBy { it.second - it.first + 1}`

[no]

actually yes, [2,5] includes 4

[Jakub Pi]

Use a half-closed interval for these kinds of things - in math notation [a, b) The reason is it makes a lot of the calculations more natural. How would you express a gap of 1 between intervals? When using closed intervals [1,3], [5,7] is really awkward. You'll always have to deal with off-by-one adjustments