INFOMAN брой 10

{ This is the input data:  N;  Beg1 End1;  Beg2 End2;  ...;  BegN EndN;
 11
 1 6
 13 14
 2 4
 4 5
 3 13
 6 7
 4 8
 7 10
 9 12
 6 9
 9 11
                            КОНГРЕСЕН ЦЕНТЪР
                            ----------------

       Един конгресен център може да е домакин на най-много една проява през
 всеки ден от годината, като всяка проява трае един или няколко последовател-
 ни дни. Центърът получава N заявки за различни прояви, като за всяка е посо-
 чен първият и последният ден. Да се напише програма,която пресмята максимал-
 ния брой заявки, които центърът може да изпълни.

       Анализ на задачата: В задачата са дадени N интервала от време и се ис-
 ка да се намери максимален брой интервали,  които не се засичат един с друг.
 Нека да дефинираме една функция F(x), която да връща максималния брой интер-
 вали, които завършват най-късно в деня x и не се засичат. Тогава
    F(0) = 0
    F(x) = F(x-1) ако в ден x не завършва нито една проява
    F(x) = Max( F(beg-1)+1 ) където за beg се вземат началните дни на всички
                             прояви, завършващи в деня x
 Търсената стойност е F(last), където last е последният ден, за който има ня-
 каква заявка. Верността на формулите е очевидна.
       РЕШЕНИЕ: Алгоритъмът,който изведохме при анализа на задачата я решава
 напълно, но все пак не е най-добрият, защото изисква памет в размер на броя
 на дните, в които работи конгресния център. Освен това има по-ефективен, ал-
 горитъм, който зависи само от броя на заявките. Да сортираме интервалите от
 време в нарастващ ред по деня, в който завършват.  От горните формули се за-
 белязва, че F(x) = 1 за най-ранния ден x, в който завършва някоя заявка и в
 същото време F(0..x-1)=0. Това означава, че заявката, която завършва най-ра-
 но винаги участва в решението на задачата.  Тя обаче може да се засича с ня-
 кои други заявки. Това означава, че те задължително не участват в решението.
 Ако премахнем тези заявки и заявката, която свършва първа,  получаваме ситу-
 ация, подобна на началната. В тази ситуация отново премахваме заявката, коя-
 то свършва първа заедно с всички засичащи се с нея заявки.Ето защо можем да
 използваме следния greedy алгоритъм за намиране на оптимално решение: сорти-
 раме заявките по техния край;  докато можем, избираме тази с най-ранен край,
 такава, че да не се засича с предходната.  Това гарантира намирането на мак-
 сималния брой заявки, които залата може да изпълни.
 На базата горните формули може да се реши не само дадената задача, но и ней-
 ният по-сложнен вариант,  в който заявките носят печалба на залата и се тър-
 си максимална печалба. Тогава последната формула можем да заместим със след-
 ната:
     F(x) = Max( F(beg-1)+value ) където за beg се вземат началните дни на
     всички прояви, завършващи в деня x, а за value съответните им печалби
 В конкретната програма се намира и извежда само максималния брой заявки, но
 ако се интересуваме и от самите заявки, можем да ги отпечатваме по време на
 намирането им.  Алгоритъма има линейна сложност, но паради сортирането слож-
 ността се увеличава до N.logN.  За простота в конкретната програма се изпол-
 зва сортиране чрез пряка селекция и алгоритъма има сложност N*N.
}

{$R-,S-,Q-}
CONST MaxN = 1000;
      InFileName  = 'CEN.PAS';
      OutFileName = '';


TYPE TTask = record b,e:integer; end;


VAR N: integer;
    Z: array[1..MaxN] of TTask;


Procedure ReadData; { Read the input data - N, Z[1..N] }
Var F: Text;
Begin
  Assign(F,InFileName); Reset(F); ReadLn(F);
  ReadLn(F,N);
  for N:= 1 to N do
    with Z[N] do
      Read(F,b,e);
  Close(F);
End;


Procedure SortData; { Sort the list of tasks by 'end time' }
  Procedure Swap(var a,b:TTask);
  Var Tmp: TTask;
  Begin Tmp:=a; a:=b; B:=Tmp; End;
Var I,J: integer;
Begin
  for I:= 1 to N-1 do
    for J:= I+1 to N do
      if Z[J].e < Z[I].e then
        Swap(Z[J],Z[I]);
End;


Procedure FindBestShedule; { Find the solution }
Var I, Left, Count: integer;
    OutF: Text;
Begin
  { finding the maximal number of tasks - Count }
  Left:=0; Count:=0;
  for I:= 1 to N do
    if Z[I].b > Left then
      begin Inc(Count); Left:=Z[I].e; end;
  { writing the result }
  Assign(OutF,OutFileName); Rewrite(OutF);
  WriteLn(OutF,Count);
  Close(OutF);
End;


BEGIN
  ReadData;
  SortData;
  FindBestShedule;
END.