Painting Tom Sawyer's Fence - programming on Free Pascal

Question

Tom Sawyer has many friends who paints his fence. Each friend painted contiguous part of the fence. Some planks could stay unpainted, some could be painted several times. Program must output the number of painted planks.

Input format:

First line: N smaller than 100000 - number of Tom Sawyer's friends.

N lines (for each friend): a, b smaller than 10⁹ - numbers (from the beginning of the fence) of the first painted by the person plank and the last painted by the person plank.

Example:

Input:

3
1 2
4 5
2 4

Output:

5

The problem is: program must work no more than 1 second on every test.

I've written many programs of different work ideas, but all of them are not fast enough. I work with online automatic system that checks my code on inputs that are unknown for me, and the system says on some tests that running the program takes 1.032, 1.036 seconds - more than a second.

Example of a working program (idea is to make all segments non-intersecting):

program sortirovkaI;

var a,b:array[1..100000] of longint; 
      {a - array of numbers of first planks for each person}
      {b - array of numbers of last planks for each person}
    n,m,i,j:longint;

procedure peresech(var a1,b1,a2,b2:longint);
{processing two segments [a1,b1], [a2,b2] - making them non-intersecting}

{if two segments intersect, procedure will make one of them bigger}
{ and "kill" another - make it [-1,-1]}

begin
   if (a1>b2) or (a2>b1) or (a1=-1) or (a2=-1) then
      exit;
   if a2<a1 then a1:=a2;
   if b2>b1 then b1:=b2;
   a2:=-1;
   b2:=-1;
end;

begin


   readln(n);
   for i:=1 to n do
     read(a[i],b[i]);  {filling the arrays}

   for i:=2 to n do   {for each segment, except the first}
       for j:=1 to i-1 do
         peresech(a[i],b[i],a[j],b[j]); {make it non-intersecting with every}
                                        {preceding segment}

   m:=0;  {summarize the lengths of all "not killed" segments}
   for i:=1 to n do
     if a[i]<>-1 then m:=m+b[i]-a[i]+1;


   writeln(m); {output}

end.

One more example of working program (idea is to "go" along the fence from the beginning to the end):

program sortirovkaI;

var a,b:array[1..100000] of longint;
      {a - array of numbers of first planks for each person}
      {b - array of numbers of last planks for each person}
    n,m,i,j,v,t:longint;

begin 

   readln(n);
   for i:=1 to n do
    read(a[i],b[i]);   {filling the arrays}

   {sorting the segments - a[1]<a[2]<a[3]<...<a[n]}
                      {    b[1] b[2] b[3] ... b[n]}
   {method of inserts - the fastest known on my level}
   for v:=1 to n-1 do
   begin
     i:=v;
     while (i>0) and (a[v+1]<a[i]) do i:=i-1;
     if i<v then
     begin
        t:=a[v+1];
        for j:=v+1 downto i+2 do a[j]:=a[j-1];
        a[i+1]:=t;

        t:=b[v+1];
        for j:=v+1 downto i+2 do b[j]:=b[j-1];
        b[i+1]:=t;
     end;
   end;


   {now start going along the fence}

   t:=b[1];  {t is the number of current plank}
   m:=b[1]-a[1]+1;  {m is the number of painted planks that we've already seen}

   for i:=2 to n do   {consider every segment}
   begin
      if a[i]>t then   {we see ahead some non-painted planks}
                       { and then current segment}
      begin
         m:=m+b[i]-a[i]+1; {add length of segment to m}
         t:=b[i];          {go to the end of the segment}
      end
      else    {the beginning of the segment is somewhere behind us}
      if b[i]>t then    {but we can see ahead the ending of the segment}
      begin
          m:=m+b[i]-t;  {add to m the way from "here" to the end of current segment}
          t:=b[i];   {go to the end of the segment}
      end;
   end;

   {we need sorting because while going along the fence we can go only forward}

   writeln(m);  {output}

end.

One more example of code - the last idea, but without sorting the arrays:

program sortirovkaI;

var a,b:array[1..100000] of longint;
    n,m,i,j,t,bmax,r:longint;
    f:boolean;


begin


   readln(n);
   for i:=1 to n do   {input}
     read(a[i],b[i]);

   bmax:=b[1];
   for i:=1 to n do    {searching for the max element n array B }
     if b[i]>bmax then bmax:=b[i];  { - the end of the fence}

   j:=1;
   for i:=1 to n do
      if a[i]<a[j] then j:=i;  {searching for the index of min element in array A}
  t:=a[j];
  a[j]:=a[1];   {making the first segment start with min value}
  a[1]:=t;      {changing a[1],b[1] and a[j],b[j]}
  t:=b[j];
  b[j]:=b[1];
  b[1]:=t;


   {now start going along the fence}
   t:=b[1];  {t is the number of current plank}
   m:=b[1]-a[1]+1;  {m is the number of painted planks that we have already seen}
   a[1]:=-1; b[1]:=-1;  {kill the segment}

 repeat 
   f:=false;
   for i:=2 to n do
   begin
      if t=bmax then  {if it is end of the fence}
      begin
         writeln(m);
         exit;
      end;
      if a[i]=-1 then continue; {if the segment is killed}
      if a[i]<=t+1 then   {if ahead us are painted planks of current segmant}
      begin
        if b[i]>t then
        begin
          m:=m+b[i]-t;  {add to m number of planks from here to the end of current segment}
          t:=b[i];  {go to the end of the segment}
        end;
        a[i]:=-1; b[i]:=-1;  {kill the segment}
        f:=true;
      end;
   end;
   if not f then {if there are non-painted planks ahead}
   begin

     i:=1;
     while a[i]<t do i:=i+1;  {searching for the index of min element in array A}
     j:=i;                     {it is number of the first painted plank we can see}
     for i:=i to n do
       if (a[i]<a[j]) and (a[i]>t) then j:=i;

    r:=a[j];
    a[j]:=a[1]; 
    a[1]:=r;     {making the first segment start with min value}
    r:=b[j];
    b[j]:=b[1];
    b[1]:=r;

     t:=b[1];  {t is the number of current plank}
     m:=m+b[1]-a[1]+1;  {m is the number of painted planks that we have already seen}
     a[1]:=-1; b[1]:=-1;  {kill the segment} 

  end;
until t=bmax;  {until we reach the end of the fence}

   writeln(m);  {output}

end.

This last one is the fastest, but still takes more than a second on some tests.

Answer 1

Because of this, the first algorithm is of the order \$O(n^2)\$:

   for i:=2 to n do   {for each segment, except the first}
       for j:=1 to i-1 do

The second algorithm is also of the order \$O(n^2)\$, because of the insertion sort. Every insertion involves both a search and shifting elements to make room for the insertion.

The third algorithm appears to be of the order \$O(n^2)\$ as well.

You do need to sort, but it should not be an insertion sort. You want a fast in-place sort such as quicksort. Quicksort is, on average, of the order \$O(n log(n))\$. Once you have that (use a library sort, if available), then the second algorithm should do much better.