Question

How to add a new interval into a sorted array of non‑overlapping intervals in Pascal

Answer 1

program InsertIntervalProgram;

type
  Interval = record
    startv: Integer;
    endv: Integer;
  end;

  IntervalArray = array of Interval;

// Helper to append an interval to a dynamic array
procedure AppendInterval(var arr: IntervalArray; iv: Interval);
var
  n: Integer;
begin
  n := Length(arr);
  SetLength(arr, n + 1);
  arr[n] := iv;
end;

// Insert a new interval into a sorted list of non-overlapping intervals
function InsertInterval(const intervals: IntervalArray; newInterval: Interval): IntervalArray;
var
  resultArr: IntervalArray;
  i, n: Integer;
  iv: Interval;
begin
  SetLength(resultArr, 0);
  i := 0;
  n := Length(intervals);

  // 1. Add all intervals that end BEFORE the new interval starts.
  // These cannot overlap.
  while (i < n) and (intervals[i].endv < newInterval.startv) do
  begin
    AppendInterval(resultArr, intervals[i]);
    Inc(i);
  end;

  // 2. Merge all intervals that DO overlap with the new interval.
  // Overlap condition: intervals[i].start <= newInterval.end
  while (i < n) and (intervals[i].startv <= newInterval.endv) do
  begin
    if intervals[i].startv < newInterval.startv then
      newInterval.startv := intervals[i].startv;
    if intervals[i].endv > newInterval.endv then
      newInterval.endv := intervals[i].endv;
    Inc(i);
  end;

  // Add the merged interval
  AppendInterval(resultArr, newInterval);

  // 3. Add all remaining intervals (those starting AFTER new interval ends)
  while (i < n) do
  begin
    AppendInterval(resultArr, intervals[i]);
    Inc(i);
  end;

  InsertInterval := resultArr;
end;

procedure PrintIntervals(const arr: IntervalArray);
var
  i: Integer;
begin
  for i := 0 to High(arr) do
    Write('[', arr[i].startv, ',', arr[i].endv, '] ');
  Writeln;
end;

var
  intervals, updated: IntervalArray;
  new1, new2: Interval;

begin
  // Initial intervals: sorted and non-overlapping
  SetLength(intervals, 3);
  intervals[0].startv := 1;  intervals[0].endv := 3;
  intervals[1].startv := 6;  intervals[1].endv := 8;
  intervals[2].startv := 13; intervals[2].endv := 18;

  new1.startv := 9;  new1.endv := 11;
  updated := InsertInterval(intervals, new1);

  new2.startv := 2;  new2.endv := 5;
  updated := InsertInterval(updated, new2);

  Writeln('Updated intervals:');
  PrintIntervals(updated);
end.



(*
run:

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

*)

 

70+ SQL courses for beginners and professionals