wersja2

using System;

struct atrakcja
{
    public int start;
    public int koniec;

    public atrakcja(int s, int f)
    {
        this.start = s;
        this.koniec = f;
    }
}


class Program
{
    static void Wybor(atrakcja[] a, int[] w, int max, int min)
    {
        // w to tablica największej liczby atrakcji do chwili i

        w[0] = 0;

        int i = 0;

        int j = 0; // indeks atrakcji

        for (i = 1; i < max - min + 1; i++)
        {
            w[i] = w[i - 1]; // wynik nie gorszy niż chwilę wcześniej
            // jeśli w tym momencie nie skończy się żadne wydarzenie
            // to ten wynik się nie zmieni
            // poniżej sorawdzę czy przypadkiem coś się nie skońćzy
            // teraz kolejno sprawdzam czy o danym czasie zakonczenia mogę dołożyć zajęcia tak aby poprawic wynik
            // ponieważ wydarzenia nie sa posortowane idę przez wszystkie także te już wykorzystane
            for (j = 0; j < a.Length; j++)
            {
                // czy gdy dodam 1 do najlepszego wyniku w momencie startu wydarzenia które się kończy
                // to wynik się poprawi? jeśli tak biorę ten poprawiony
                if (a[j].koniec - min == i && w[a[j].start - min] + 1 > w[i]) // (a[j].f - min) jest równe i
                {
                    w[i] = w[a[j].start - min] + 1;
                }
            }
        }
        // Złożoność O( (max-min) * a.Length )
    }

    static void Main(string[] args)
    {
        atrakcja[] a ={new atrakcja (3,6), new atrakcja (1,3), new atrakcja (13,15),

            new atrakcja (2,3), new atrakcja(1,2), new atrakcja (4,7), new atrakcja (11,12),

            new atrakcja (8,11), new atrakcja (7,10), new atrakcja (11,14),

            new atrakcja (5,9), new atrakcja(2,5), new atrakcja(1,5)};

        int min = int.MaxValue;
        int max = int.MinValue;

        for (int i = 0; i < a.Length; i++)
        {
            if (a[i].start < min) min = a[i].start;
            if (a[i].koniec > max) max = a[i].koniec;
        }

        int[] v = new int[max - min + 1];// wynik

        Wybor(a, v, max, min);

        for (int i = 0; i <= max - min; i++)

            Console.WriteLine("dla {0} max = {1}", i + 1, v[i]);

        Console.ReadKey();
    }
}