Question

How to add a new interval into a sorted vector of non‑overlapping intervals in Rust

Answer 1

fn insert_interval(intervals: Vec<[i32; 2]>, mut new_interval: [i32; 2]) -> Vec<[i32; 2]> {
    let mut result = Vec::new();
    let mut i = 0;
    let n = intervals.len();

    // 1. Add all intervals that end BEFORE the new interval starts.
    // These cannot overlap.
    while i < n && intervals[i][1] < new_interval[0] {
        result.push(intervals[i]);
        i += 1;
    }

    // 2. Merge all intervals that DO overlap with the new interval.
    // Overlap condition: intervals[i].start <= new_interval.end
    while i < n && intervals[i][0] <= new_interval[1] {
        new_interval[0] = new_interval[0].min(intervals[i][0]);
        new_interval[1] = new_interval[1].max(intervals[i][1]);
        i += 1;
    }

    // Add the merged interval
    result.push(new_interval);

    // 3. Add all remaining intervals (those starting AFTER new interval ends)
    while i < n {
        result.push(intervals[i]);
        i += 1;
    }

    result
}

fn main() {
    let intervals = vec![[1, 3], [6, 8], [13, 18]];
    let new_interval1 = [9, 11];

    let updated = insert_interval(intervals, new_interval1);

    let new_interval2 = [2, 5];
    let updated = insert_interval(updated, new_interval2);

    println!("Updated intervals:");
    for iv in updated {
        print!("[{},{}] ", iv[0], iv[1]);
    }
}


/*
run:

Updated intervals:
[1,5] [6,8] [9,11] [13,18] 

*/

 

70+ SQL courses for beginners and professionals