Imports System
Imports System.Collections.Generic
Module InsertIntervalProgram
Function InsertInterval(intervals As List(Of Integer()), newInterval As Integer()) As List(Of Integer())
Dim result As New List(Of Integer())()
Dim i As Integer = 0
Dim n As Integer = intervals.Count
' 1. Add all intervals that end BEFORE the new interval starts.
' These cannot overlap.
While i < n AndAlso intervals(i)(1) < newInterval(0)
result.Add(intervals(i))
i += 1
End While
' 2. Merge all intervals that DO overlap with the new interval.
' Overlap condition: intervals(i).start <= newInterval.end
While i < n AndAlso intervals(i)(0) <= newInterval(1)
newInterval(0) = Math.Min(newInterval(0), intervals(i)(0))
newInterval(1) = Math.Max(newInterval(1), intervals(i)(1))
i += 1
End While
' Add the merged interval
result.Add(newInterval)
' 3. Add all remaining intervals (those starting AFTER new interval ends)
While i < n
result.Add(intervals(i))
i += 1
End While
Return result
End Function
Sub Main()
Dim intervals As New List(Of Integer()) From {
New Integer() {1, 3},
New Integer() {6, 8},
New Integer() {13, 18}
}
Dim newInterval1 As Integer() = {9, 11}
Dim updated = InsertInterval(intervals, newInterval1)
Dim newInterval2 As Integer() = {2, 5}
updated = InsertInterval(updated, newInterval2)
Console.WriteLine("Updated intervals:")
For Each iv In updated
Console.Write("[" & iv(0) & "," & iv(1) & "] ")
Next
Console.WriteLine()
End Sub
End Module
' run:
'
' Updated intervals:
' [1,5] [6,8] [9,11] [13,18]
'
