Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.

Source

package questions

import _utils.UseCommentAsDocumentation
import utils.assertIterableSame
import java.util.*


/**
 * You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [starti, endi]`
 * represent the start and the end of the ith interval and intervals is sorted in ascending order by `starti`.
 * You are also given an interval `newInterval = [start, end]` that represents the start and end of another interval.
 *
 * Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `starti` and
 * `intervals` still does not have any overlapping intervals (merge overlapping intervals if necessary).
 * Return `intervals` after the insertion.
 *
 * [Source](https://leetcode.com/problems/insert-interval/)
 */
@UseCommentAsDocumentation
private fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
    if (intervals.isEmpty()) {
        return arrayOf(newInterval)
    }

    fun hasOverlap(current: IntArray, intervalInHand: IntArray): Boolean {
        val range1 = current.first()..current.last()
        val range2 = intervalInHand.first()..intervalInHand.last()
        return intervalInHand[0] in range1 || intervalInHand[1] in range1 || current[0] in range2 || current[1] in range2
    }

    fun isSelfInBetweenPrevAndCurrent(prev: IntArray, current: IntArray, self: IntArray): Boolean {
        return self.first() > prev.last() && self.last() < current.first()
    }


    fun isLessThanFirst(): Boolean {
        return newInterval.last() < intervals.first().last()
    }

    fun isHigherThanLast(): Boolean {
        return newInterval.first() > intervals.last().last()
    }


    fun merge(vararg _intervals: IntArray): IntArray {
        return intArrayOf(_intervals.map { it[0] }.minOrNull()!!, _intervals.map { it[1] }.maxOrNull()!!)
    }

    val result = arrayListOf<IntArray>()

    fun getLatestAddedElem(): IntArray {
        return result.last()
    }

    // check if whether [newInterval] should be inserted before [intervals] i.e. no overlaps with the first
    if (isLessThanFirst() && !hasOverlap(intervals.first(), newInterval)) {
        result.add(newInterval)
        result.addAll(intervals)
        return result.toTypedArray()
    }
    // check if whether [newInterval] should be inserted after [intervals] i.e. no overlaps with the last
    if (isHigherThanLast() && !hasOverlap(intervals.last(), newInterval)) {
        result.addAll(intervals)
        result.add(newInterval)
        return result.toTypedArray()
    }

    // add first interval immediately
    // the latest value of [result] is what we will be merging with [newInterval]
    result.add(intervals.first())

    // loop till the size not the index as it might be required to merge [newIntervals] with the last element
    for (i in 1..intervals.size) {

        // [newInterval] has overlap with [result]'s latest so merge them and replace
        if (hasOverlap(getLatestAddedElem(), newInterval)) {
            val latestAddedInterval = result.removeAt(result.lastIndex) // remove
            result.add(merge(latestAddedInterval, newInterval))         // merge and add
        }

        // now do same for the [current]
        val current = intervals.getOrNull(i)

        if (current != null) {  // since we are looping till size
            if (hasOverlap(current, getLatestAddedElem())) {
                // [current] overlaps with the [result] so merge them
                val latestAddedInterval = result.removeAt(result.lastIndex)
                result.add(merge(latestAddedInterval, current))
            } else {
                // [current] doesn't require merging so, it should be added to [result]

                // However, it is possible that the [newInterval] lies in between [current] & [result] WITHOUT overlaps
                //
                // In this case, the [newInterval] is added as it is to the final [result] and then [current] is added
                if (isSelfInBetweenPrevAndCurrent(prev = getLatestAddedElem(), current = current, self = newInterval)) {
                    result.add(newInterval)
                }
                result.add(current)
            }
        }
    }
    return result.toTypedArray()
}

fun main() {

    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(3, 5), intArrayOf(12, 15)),
            newInterval = intArrayOf(6, 6)
        ).toList(),
        expected = arrayOf(intArrayOf(3, 5), intArrayOf(6, 6), intArrayOf(12, 15)).toList()
    )


    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(1, 2)),
            newInterval = intArrayOf(2, 7)
        ).toList(),
        expected = arrayOf(intArrayOf(1, 7)).toList()
    )

    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(1, 5)),
            newInterval = intArrayOf(1, 7)
        ).toList(),
        expected = arrayOf(intArrayOf(1, 7)).toList()
    )

    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(1, 5)),
            newInterval = intArrayOf(2, 7)
        ).toList(),
        expected = arrayOf(intArrayOf(1, 7)).toList()
    )
    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(1, 3), intArrayOf(6, 9)),
            newInterval = intArrayOf(2, 5)
        ).toList(),
        expected = arrayOf(intArrayOf(1, 5), intArrayOf(6, 9)).toList()
    )
    assertIterableSame(
        actual = insert(
            intervals = arrayOf(
                intArrayOf(1, 2),
                intArrayOf(3, 5),
                intArrayOf(6, 7),
                intArrayOf(8, 10),
                intArrayOf(12, 16)
            ),
            newInterval = intArrayOf(4, 8)
        ).toList(),
        expected = arrayOf(intArrayOf(1, 2), intArrayOf(3, 10), intArrayOf(12, 16)).toList()
    )

    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(3, 5)),
            newInterval = intArrayOf(1, 2)
        ).toList(),
        expected = arrayOf(intArrayOf(1, 2), intArrayOf(3, 5)).toList()
    )

    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(3, 5)),
            newInterval = intArrayOf(3, 5)
        ).toList(),
        expected = arrayOf(intArrayOf(3, 5)).toList()
    )


    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(1, 5)),
            newInterval = intArrayOf(2, 3)
        ).toList(),
        expected = arrayOf(intArrayOf(1, 5)).toList()
    )





    assertIterableSame(
        actual = insert(
            intervals = arrayOf(intArrayOf(1, 5)),
            newInterval = intArrayOf(6, 8)
        ).toList(),
        expected = arrayOf(intArrayOf(1, 5), intArrayOf(6, 8)).toList()
    )


}

View on GitHub

Updated on 2022-10-02