Wyznaczenie minimalnej liczby rozłączych przedziałów

Witam, wiem że na forum znajduję się już temat z identycznym problemem, jednak jest on przedstawiony dla języka C++, którego nie zdążyłem jeszcze przyswoić.

Zadanie znajdziecie pod tym linkiem:
http://main.edu.pl/pl/user.phtml?op=showtask&task=prze&con=PAS

Po wysłaniu odpowiedzi dostaje 40/100pkt.
Z tego co widzę to problem zaczyna się, jeśli przedziałów jest więcej niż 200 (przy 200 jeszcze mi zalicza). Chociaż może to zwykły zbieg okoliczności i wszystko zależy od sposobu rozmieszczenia przedziałów w ciągu i od mojego błędnego algorytmu.

Oto kod programu:

 type tablica = array[1..5000] of longint;
var x,y : tablica;
    n,k,i,j,p,z : longint;
    a,b : longint;
    c : byte;

begin
k:=2;
readln(n);
read(x[1]);
readln(y[1]);

for i:=2 to n do
  begin
   z:=0;
   read(a);
   readln(b);
   for j:=1 to k-1 do
     begin
      if (a<=y[j]) and (b>=x[j]) or
         (x[j]>=a) and (y[j]<=b) or
         (a=y[j]+1) or (b=x[j]-1) then
        begin
         if a<x[j] then
           x[j]:=a;
         if b>y[j] then
           y[j]:=b;
         z:=z+1;
         break;
        end
      else
      if (z=0) and (j=k-1) then
        begin
         x[k]:=a;
         y[k]:=b;
         k:=k+1;
        end;
     end;
  end;

z:=0;
if k>2 then
begin
repeat
  for i:=1 to k-2-z do
   begin
   c:=0;
    for j:=i+1 to k-1-z do
      begin
       if (x[i]=y[j]+1) then
         begin
          x[i]:=x[j];
          c:=c+1;

          for p:=j to k-1-z do         {przsun}
            begin
             x[p]:=x[p+1];
             y[p]:=y[p+1];
            end;

          z:=z+1;
          break;
         end;
       if (y[i]=x[j]-1) then
         begin
          y[i]:=y[j];
          c:=c+1;

          for p:=j to k-1-z do         {przsun}
            begin
             x[p]:=x[p+1];
             y[p]:=y[p+1];
            end;

          z:=z+1;
          break;
         end;
      end;
    if c>0 then
    break;
   end;
until i=k-2-z;
end;

writeln(k-1-z);
end.

Wiem że kod jest mało profesjonalny i nazwy zmiennych nic nie mówią, dlatego w razie wątpliwości proszę pytać.

Algorytm wygląda mniej więcej tak:

1. W dwie tablice wpisuje dane.
   W tablice "x" pierwszą współrzędną przedziału, a w "y" drugą.
   Na początku tablice mają tylko jeden element. Po wpisaniu kolejnego sprawdzane jest czy będzie tworzył wspólny przedział z pierwszym (przypominam że to przedziały liczb całkowitych, dlatego nawet jeśli będą położone +/- 1 obok siebie będą wspólnym przedziałem). Jeśli nie, dopisywany jest kolejny element do tablic. Jednocześnie zwiększana jest zmienna "k". Itd...

2. Po umieszczeniu wszystkich przedziałów jeszcze raz sprawdzane jest, czy aby na pewno nie leżą "koło siebie". Jeśli tak parametry zostają zmienione, zmienna "z" wzrasta o 1, a elementy tablic zostają przesunięte.

3. Na wyjściu wynik: różnica liczby "k' i "z".

Proszę o wskazówki gdzie popełniłem błąd.

Wczytujesz 2 liczby, sumujesz je i w tablicy gdzie indeksami są sumy liczb w przedziale zwiększasz daną komórkę o 1. Następnie liczysz ile jest wartości większych od 1 i wypisujesz wynik na wyjście.

przed chwilą zrobiłem to zadanie w c++ i dostałem 100pkt i najłatwiej to zrobić tak:

1. Sortujesz przedziały po początkach, w przypadku takich samych początków pierwszy powinien pojawić się z większym końcem.
2. Tworzysz 3 zmienne: ilosc_roznych, poczatek_ostatniego, koniec_ostatniego i inicjujesz je wartosciami kolejno: 0, -1000000001, -1000000001, chodzi o to, że zakładasz, że kiedyś wystąpił już przedział ale jest tak daleko z lewej, że na pewno kolejny przedział na niego nie najdzie, przez co pierwszy przedział na pewno nie połączy się z poprzednim.
3. Dla każdego przedziału (posortowanego) idąc od lewej wykonujesz:
   a) sprawdzasz czy pocztek_ostatniego jest rozny od aktualnego poczatku, jeśli nie to przechodzisz do kolejnego przedziału (continue w pętli).
   b) sprawdzasz czy warunek: koniec_ostatniego+1>=poczatek_aktualnego jest sprawdzony, jeśli tak to ustawiasz jako koniec_ostatniego = max(koniec_ostatniego, koniec_aktualnego), jeśli warunek nie spełniony to zwiększasz ilosc_roznych o 1 oraz ustawiasz koniec_ostatniego = koniec_aktualnego
   c) ustawiasz poczatek_ostatniego = poczatek_aktualnego
4. Wypisujesz wynik (ilosc_roznych)

kod w c++ (powinien być w miarę czytelny):

// te linie sa niewazne
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// struktura przechowujaca przedzial, int oznacza liczbe calkowitą 32 bitową
struct Przedzial
{
  int a,b;
};


// funkcja porownujaca dwa przedzialy
bool przed_porown(const Przedzial& a, const Przedzial& b)
{
  return (a.a==b.a && a.b > b.b) || a.a<b.a;
}

// tutaj zaczyna sie program
int main()
{
  // ta linia jest nie wazna
  ios_base::sync_with_stdio(0);
  int n;
  // wczytanie n
  cin >> n;
  // utworzenie tablicy przedzialow
  vector<Przedzial> przed(n);
  // wczytanie jej
  for (int i=0; i<n; i++)
    {
      cin >> przed[i].a >> przed[i].b;
    }

  // sortowanie
  sort(przed.begin(),przed.end(),przed_porown);
  int roznych = 0;
  int koniec_ost = -1000000001;
  int ost = -1000000001;
  // odpowiednik: for i:=0 to n-1 do
  for (int i=0; i<n; i++)
    {
      // tworzenie aliasu do aktualnego przedzialu, aktualny przedzial od teraz nazywa sie curr
      const Przedzial& curr = przed[i];

      if (ost==curr.a)
        continue;

      if (koniec_ost+1>=curr.a)
        {
          koniec_ost = max(koniec_ost,curr.b);
        }
      else
        {
          roznych++;
          koniec_ost = curr.b;
        }
      ost = curr.a;
    }
  // wypisanie wyniku
  cout << roznych << endl;
  // program zakonczyl sie bez bledow, zwraca 0 do systemu (odpowiednik Exit(0))
  return 0;
}

Mi się wydaje, że nie trzeba sortować po końcach. No chyba, że ktoś będzie miał kontrprzykład :)

#include <algorithm>
#include <iostream>

struct przedzial {
    int a, b;
    bool operator<(const przedzial &that) const {
        return a < that.a;
    }
};

int main() {
    int n;
    std::cin >> n;
    przedzial *t = new przedzial[n];
    for (int i = 0; i < n; i++)
        std::cin >> t[i].a >> t[i].b;
    std::sort(t, t + n);
    int r = t[0].b;
    int d = 1;
    for (int i = 1; i < n; i++) {
        if (t[i].a <= r + 1) {
            r = std::max(r, t[i].b);
        } else {
            d++;
            r = t[i].b;
        }
    }
    delete [] t;
    std::cout << d << std::endl;
}

Chłopaki, dzięki za odpowiedzi, ale tak jak mówiłem nic nie rozumiem z kodów w C++.
Może ktoś mógłby spróbować przedstawić to w Pascalu?

Próbowałem też tak:

 type przedz = record
  x : longint;
  y : longint;
end;

     tablica = array[1..5002] of przedz;

var t : tablica;
    n,i,j,licznik,znacznik : word;


procedure zamiana(var a,b: przedz);
var pom : przedz;
begin
 pom:=a;
 a:=b;
 b:=pom;
end;

procedure sort(n: integer);
var i,j : integer;
begin
for i:=n downto 2 do
  for j:=1 to n-(n-(i-1)) do
    if ((t[i].x) < (t[j].x))
    or ((t[i].x) = (t[j].x)) and ((t[i].y) > (t[j].y)) then
      zamiana(t[i],t[j]);
end;

begin
readln(n);
for i:=1 to n do
  begin
   read(t[i].x);
   readln(t[i].y);
  end;
sort(n);

znacznik:=1;
licznik:=1;
repeat
for i:=znacznik to n-1 do
 begin
  for j:=i+1 to n do
    if t[i].y+1 < t[j].x then
      begin
       licznik:=licznik+1;
       znacznik:=j;
       break;
      end;
  break;
 end;
until j=n;

writeln(licznik);
end.

Jednak znowu 40/100pkt.

to że nie rozumiesz kodów, to jest już Twój wymysł. Nawet nie spojrzałeś na mój kod, bo gdybyś spojrzał na mój kod to zobaczyłbyś komentarze.

{ = begin
} = end
if = if
= then (nie ma)
struct Przedzial = Przedzial = record
cout << roznych << endl; = WriteLn(roznych);

czego nie rozumiesz?

zmienne robisz tak:
int a;

zamiast tak:
var
a: integer;

i możesz je "tworzyć" w dowolnym momencie.

mówienie, że nic nie rozumiesz z C++ jest ograniczające i świadczące o Twoim lenistwie.

1. w twoim kodzie zamula Ci na pewno sortowanie, które ma złożoność O(n^2) zamiast O(n log n). skopiuj sobie quicksorta w pascalu z neta, jeśli nie ma tam go w jakiejś bibliotece

2. nie zrobiłeś swojego algorytmu tak jak Ci napisalismy tylko po swojemu algorytmem dużo wolniejszym.

Przepraszam że odpisuje po paru dniach, ale niestety nie miałem możliwości skorzystania z internetu.

krwq napisał(a)

to że nie rozumiesz kodów, to jest już Twój wymysł. Nawet nie spojrzałeś na mój kod, bo gdybyś spojrzał na mój kod to zobaczyłbyś komentarze.

Na prawdę uważasz, że jestem na tyle nienormalny, aby najpierw zadawać pytanie w interesującej mnie kwestii, a później po prostu ignorować odpowiedzi?
Z programowaniem zetknąłem się po raz pierwszy w życiu jakieś półtora miesiąca temu. Pomyślałem, że na początku nauczę się Pascala. Później trafiłem na stronę z której pochodzi zadanie i postanowiłem, że po kolei przerobię lekcje kursów tam dostępnych.
Do C++ jeszcze nie doszedłem i nie zamierzałem zaprzątać sobie tym głowy dopóki nie ogarnę lepiej Pascala.
Nie bez powodu umieściłem mój post w dziale "Pascal" oczekując pomocy w tym języku.
Oczywiście nie oczekuję gotowego programu. Chciałbym zrozumieć algorytm. Dlatego byłbym wdzięczny gdybyś trochę jaśniej nakreślił metodę rozumowania w tym przypadku, bo nie za bardzo ogarniam o co chodzi z tymi trzema zmiennymi: "ilosc_roznych, poczatek_ostatniego, koniec_ostatniego".

krwq napisał(a)

1. w twoim kodzie zamula Ci na pewno sortowanie, które ma złożoność O(n^2) zamiast O(n log n). skopiuj sobie quicksorta w pascalu z neta, jeśli nie ma tam go w jakiejś bibliotece

Raczej nie ma to znaczenia, ponieważ w kursie podane są tylko 3 rodzaje sortowania (wszystkie mają złożoność O(n^2)). Myślę że zadanie da się rozwiązać jednym z tych sortowań (nie kazali by zrobić czegoś, czego nie uczyli).

krwq napisał(a)

2. nie zrobiłeś swojego algorytmu tak jak Ci napisalismy tylko po swojemu algorytmem dużo wolniejszym.

Ponieważ tak jak powiedziałem nie zrozumiałem Twojego objaśnienia algorytmu.

Na koniec chciałbym zapytać czy ktoś orientuje się, na podstawie kodów programów, które umieściłem powyżej,gdzie jest błąd przez który nie zostają zaliczone.

Oczywiście nie oczekuję gotowego programu. Chciałbym zrozumieć algorytm.

Ponieważ tak jak powiedziałem nie zrozumiałem Twojego objaśnienia algorytmu.

No przecież podali Ci w C++. To lepiej niż w języku migowym czy krokowym/blokowym gdyż składnia jest JEDNOZNACZNA, wystarczy że poświęcisz minimalny czas aby się jej nauczyć. Ale ty sam nie wiesz czego chcesz, dają algorytm, to źle, ale nie chcesz kodu w pascalu. No to czego chcesz? No bo ja nie rozumiem. Chcesz gotowca, tak? Oczekujesz że dostosujemy się do ciebie? To raczej ty powinieneś się postarać zrozumieć odpowiedź.

Na koniec chciałbym zapytać czy ktoś orientuje się, na podstawie kodów programów, które umieściłem powyżej,gdzie jest błąd przez który nie zostają zaliczone.

1. Zostają zaliczone, na 40p.
2. Wolny algorym/słabo zaimplementowany. np takie coś jak
   tablica = array[1..5002] of przedz;
   Już znaczy że wiesz mało o programowaniu... Ja rozumiem że jesteś nowy itd., ale no ale umiejętność pisania szybkich i dobrych programów wychodzi z czasem.
   Dostałeś masę odpowiedzi, poświęć czas na ich analizę a nie mówisz że nie rozumiesz itd.

Oho napisał(a)

2. Wolny algorym/słabo zaimplementowany(...)

Tak wygląda tabela z wynikami:

http://desmond.imageshack.us/Himg41/scaled.php?server=41&filename=maintz.jpg&res=medium
(nie wiem dlaczego, ale nie da się wstawić wygodniejszej formy linku lub po prostu obrazka)

Jak widać najdłuższy program trwa 0,09s, czyli mieści się w 10s.
W przeciwnym wypadku napisane byłoby: "program wywłaszczony".
Dlatego wydaje mi się (może się nie znam), że mimo iż twierdzicie, że algorytm jest wolny, to nie ma to w tym przypadku znaczenia, ponieważ i tak jest wystarczająco szybki, aby zmieścić się w limicie.
Problemem jest to, że przy większej ilości danych i większych liczbach program wyświetla za duże wyniki, co widać w wierszach z indeksami pod tabelą.

Oho napisał(a)

No to czego chcesz? No bo ja nie rozumiem. Chcesz gotowca, tak? Oczekujesz że dostosujemy się do ciebie? To raczej ty powinieneś się postarać zrozumieć odpowiedź.

Szczerze mówiąc, wolałbym po prostu zrozumieć co zrobiłem nie tak w moim kodzie. To by mi bardziej pomogło.

Oho napisał(a)

2. Wolny algorym/słabo zaimplementowany. np takie coś jak
   tablica = array[1..5002] of przedz;

Już znaczy że wiesz mało o programowaniu...

Zdaję sobie sprawę z tego, że mało wiem. Szkoda tylko, że nie napisałeś czym ten przykład z typem tablicowym świadczy o moim małym doświadczeniu. Może to pomogłoby mi nie popełniać podobnych błędów w przyszłości.
Ale niestety, gdy przegląda się to forum i czyta różne wątki, można zauważyć, że odpowiadającym bardziej niż na udzieleniu pomocy, zależy na połechtaniu swojego wygórowanego ego.

Jak widać najdłuższy program trwa 0,09s, czyli mieści się w 10s.
Problemem jest to, że przy większej ilości danych i większych liczbach program wyświetla za duże wyniki, co widać w wierszach z indeksami pod tabelą.

Wcześniej nie widziałem tablicy z wynikami. To co masz znaczy że jest zły algorytm lub ew. źle implementujesz go dla dużych liczb.

Szczerze mówiąc, wolałbym po prostu zrozumieć co zrobiłem nie tak w moim kodzie. To by mi bardziej pomogło.

No skoro zła odpowiedź to używasz złego algorytmu, porównaj z tym co Ci dali. Proste. I przyzwyczaj się do tego że jest w C++ bo ten język jest dosyć popularny i nauka czytania takiego kodu na pewno nie będzie stratą czasu.

Zdaję sobie sprawę z tego, że mało wiem. Szkoda tylko, że nie napisałeś czym ten przykład z typem tablicowym świadczy o moim małym doświadczeniu. Może to pomogłoby mi nie popełniać podobnych błędów w przyszłości.

Skoro chcesz wiedzieć, to raczej powinno się użyć tablicy dynamicznej (pogugluj o tym [dynamic array]). Oczywiście jest ona dostępna tylko jeżeli używasz normalnego kompilatora (czytaj: Nie TP). I nie jest to błąd, a jedynie usprawnienie.

Ale niestety, gdy przegląda się to forum i czyta różne wątki, można zauważyć, że odpowiadającym bardziej niż na udzieleniu pomocy, zależy na połechtaniu swojego wygórowanego ego.

Czyżbyś mówił o mnie? No cóż, uważaj jak chcesz. Ale Twoje zachowanie również pozostawia sporo do życzenia. Chociażby to że sam nie wiesz czego chcesz, a wszystko masz na tacy. Ja bym chciał żeby tyle osób odpowiadało na moje pytania, a często zdarza się tak że nikt nie wie albo źle odpowiada.

No dobra, w końcu sobie poradziłem.

type przedz = record
  x : longint;
  y : longint;
end;

     tablica = array[1..5002] of przedz;

var t : tablica;
    n,i,j,licznik : word;

procedure zamiana(var a,b: przedz);
var pom : przedz;
begin
 pom:=a;
 a:=b;
 b:=pom;
end;

procedure sort(n: integer);
var i,j : integer;
begin
for i:=n downto 2 do
  for j:=1 to n-(n-(i-1)) do
    if ((t[i].x) < (t[j].x))
    or ((t[i].x) = (t[j].x)) and ((t[i].y) > (t[j].y)) then
      zamiana(t[i],t[j]);
end;

begin
readln(n);
 for i:=1 to n do
   begin
    read(t[i].x);
    readln(t[i].y);
   end;
sort(n);

licznik:=0;
for i:=1 to n-1 do
 begin
  if t[i].x=1000000001 then
   continue;

  for j:=i+1 to n do
    if t[i].y+1 >= t[j].x then
      begin
       if t[i].y < t[j].y then
         t[i].y:=t[j].y;

       t[j].x:=1000000001;
       t[j].y:=1000000001;
       licznik:=licznik+1;
      end;
 end;

writeln(n-licznik);
end. 

Oho napisał(a)

Czyżbyś mówił o mnie?

Niekoniecznie tylko o Tobie.

Oho napisał(a)

Skoro chcesz wiedzieć, to raczej powinno się użyć tablicy dynamicznej (pogugluj o tym [dynamic array]). Oczywiście jest ona dostępna tylko jeżeli używasz normalnego kompilatora (czytaj: Nie TP). I nie jest to błąd, a jedynie usprawnienie.

A o tym to nie wiedziałem. Wszędzie pisali, że w Pascalu nie ma tablic dynamicznych. Widocznie to było o TP. Ja używam FPC. Zostawiłem już tak jak było, bo w tym wypadku nie ma to znaczenia. I tak i tak program mieści się w ilości wyznaczonej pamięci.
W każdym razie dziękuję za przydatną informację.