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 109 - 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:31 24 52 4Output:5The 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.
Painting Tom Sawyer's Fence - programming on Free Pascal
optimization;array;programming challenge;time limit exceeded;pascal
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 doThe 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.