Skip to content

Files

Latest commit

985d27b · Jan 30, 2025

History

History
91 lines (80 loc) · 2.62 KB

57.insert-interval.md

File metadata and controls

91 lines (80 loc) · 2.62 KB

Clarification Questions

  • No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

  • The intervals is empty.
  • The new interval is not overlapped with any intervals. (before all intervals, after all intervals, between all intervals)

Iteration

fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
    val results = mutableListOf<IntArray>()
    var i = 0

    // Add all non-overlapping interval before the new interval
    // interval[i]  newInterval
    // |---------|  |_________|
    while (i < intervals.size && intervals[i][1] < newInterval[0]) {
        results.add(intervals[i])
        i++
    }

    // intervals[i] is partially overlapped with new interval
    // |----------|
    //        |_________|
    // Or
    //      |-------|
    // |______|
    var merged = newInterval
    while (i < intervals.size && isOverlapped(intervals[i], merged)) {
    // Or equivalent to
    // while (i < intervals.size && intervals[i][0] <= merged[1]) {
        merged[0] = minOf(intervals[i][0], merged[0])
        merged[1] = maxOf(intervals[i][1], merged[1])
        i++
    }
    results.add(merged)

    // add the remaining non-overlapping intervals
    while (i < intervals.size) {
        results.add(intervals[i])
        i++
    }

    return results.toTypedArray()
}

Or equivalently, we can use for loop to iterate through the intervals. (but more complex, not recommended)

fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
    val results = mutableListOf<IntArray>()
    var merged = newInterval
    // Check if the newInterval is added.
    var isAdded = false
    for (i in 0 until intervals.size) {
        if (isOverlapped(intervals[i], merged)) {
            if (!isAdded) {
                results.add(merged)
                isAdded = true
            }
            merged[0] = minOf(merged[0], intervals[i][0])
            merged[1] = maxOf(merged[1], intervals[i][1])
        } else {
            // The newInterval is ahead of all intervals, we have to add it first.
            if (!isAdded) {
                if (merged[1] < intervals[i][0]) {
                    results.add(merged) 
                    isAdded = true
                } 
            }
            results.add(intervals[i])
        }
    }

    // The newInterval is the last interval and not overlapped with any intervals.
    if (!isAdded) results.add(merged)
    return results.toTypedArray()
}
  • Time Complexity: O(n).
  • Space Complexity: O(1).