Painting Tom Sawyer's Fence - programming on Free Pascal

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:

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 a2b1 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]<>

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.

StackExchange Code Review Q#38621, answer score: 5