Очень-очень оптимальный жадный алгоритм - C#

#c_sharp #алгоритм

Задача(у меня не совсем такая, она на другом языке, так что я просто привожу подобную).

Даны n заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны
начало и конец занятия si и fi для i-й заявки). В случае пересечения заявок можно удовлетворить
лишь одну из них. Заявки с номерами i и j совместны, если интервалы (si,fi) и (sj,fj)
не пересекаются (то есть fi < fj или fj < fi). Задача о выборе заявок состоит в том,
чтобы набрать максимальное количество совместных друг с другом заявок. 
Количество заявок и сами заявки в текстовом документе prednasky.in, то-есть:  

Ввод (текстовый документ):   


  5 - первая строчка - кол-во интервалов
  2 4 (2 - начало интервала, 4 - конец и тд)
  1 7
  6 9
  9 11
  5 8


Вывод:


  3 (максимальное количество совместных друг с другом заявок)
  1 5 4 (номера этих заявок(если есть несколько вариантов - выписать любой))  


Программу проверяет специальный сайт с тестами, и моя программа не проходит тесты
на больших числах, хотя, как мне кажется я добился временной сложности nlogn+n (с памятью
всё уже нормально, именно по скорости не проходит). Вот сам код:

     class Program
        {
                static int N;
               static int[,] a;

    static void Main(string[] args)

    {
        using (StreamReader sr = new StreamReader(@"prednasky.in"))
        {
            string line;
            line = sr.ReadLine();
            N = int.Parse(line);
            a = new int[N, 2];
            int[] indx = new int[N];
            int[] b = new int[N];
            for (int i = 0; i < N; i++)
            {
                line = sr.ReadLine();
                int[] nums = line.Trim().Split().Select(w => int.Parse(w)).ToArray();
                //начало интервалов и их идексы записываем в массив А
                a[i, 0] = nums[0];
                a[i, 1] = i + 1;
                //Концы интервалов записываем в массив б
                b[i] = nums[1];
                //заполняем массив индексов;
                indx[i] = i;
            }

            //Cортировка массива индексов по массиву б
            Array.Sort(b, indx);
            //Дальше одним циклом проходим массив а, но не по i, а по полю индексов
(для того, что бы не сортировать двумерный массив, геморно же, лучше одномерный)) 
          
            //string str = "";
            int last = 0;
            int poc = 0;
            for (int i = 0; i < N; i++)
            {
                if (a[indx[i], 0] > last)
                {
                    //в самое начало "отсортированного" массива записываем нужные
числа по порядку
                    a[indx[poc], 0] = a[indx[i], 1];
                    poc++;
                    last = b[i];
                }
            }
            using (StreamWriter sr1 = new StreamWriter(@"rozvrh.out"))
            {
                sr1.WriteLine(poc);
                for (int i = 0; i < poc; i++)
                {
                    sr1.Write(a[indx[i], 0]);
                    sr1.Write(" ");
                }
                }
        }
    }

}


Алгоритм работает, проблема только со скоростью. Любым идеям буду рад)
    

Ответы

Ответ 1

Можно отбирать среди оставшихся допустимых заявок ту, у которой время окончания наименьшее.
В этом случае мы ничего не теряем.
Кроме того, следует удалять из очереди заявки, которые не могут быть использованы.

Алгоритм может быть рекурсивным, если вызываемая процедура получает допустимое начало
интервала $start, очередь из оставшихся заявок $queue и массив принятых заявок $request. 

Программа на PHP:

$request = [1=>[2,4], [1,7], [6,9], [9,11], [5,8]];
// starting shedule

function print_1d($text, $arr){
    echo "$text";
    foreach($arr as $value) printf("%2d ", $value);
}

function print_sh($text, $arr){
    echo "$text";
    foreach ($arr as $key => $value) {
        if(gettype($value) == "array")  print_1d(" $key=>  ", $value);
        else echo " $key=>$value";
    }
}

function greedy($sh){
    global $request, $counter;
    $counter++;
    print_sh("
sh ", $sh);
    $start = $sh['start'];
    $queue = $sh['queue'];
    $accepted = $sh['accepted'];
    if(empty($queue)) return $sh;
    foreach ($queue as $key=>$number) {
        if($request[$number][0] < $start) unset($queue[$key]);
        elseif(!isset($finish) || ($request[$number][1] < $finish)) {
            $finish = $request[$number][1];
            $keynext = $key;
        }
    }
    $start = $finish + 1;
    unset($queue[$keynext]);
    $accepted[] = $keynext+1;                       // then test the variant  
    return greedy(['start'=>$start, 'queue'=>$queue, 'accepted'=>$accepted]);   //
when the request is accepted 
}

$n = count($request);
$counter = 0;
print_sh("The requests are:
",$request);
$shedule = [
    'start' => 0,
    'queue' => range(1, $n),
    'accepted'=>[]
];

echo "

The local optima are:
";
$shedule_opt = greedy($shedule);
print_sh("

Taking in account $counter variants.
The optimal variant
is:
", $shedule_opt);


Результаты:


The requests are:
 1=>   2 4  2=>   1 7  3=>   6 9  4=>   9 11  5=>   5 8 

The local optima are:

sh  start=>0 queue=>   1 2 3 4 5  accepted=>  
sh  start=>5 queue=>   2 3 4 5  accepted=>   1 
sh  start=>9 queue=>   3 4  accepted=>   1 5 
sh  start=>12 queue=>   accepted=>   1 5 4 

Taking in account 4 variants.
The optimal variant is:
 start=>12 queue=>   accepted=>   1 5 4