Условие

Judge

Прегледах записа от упражнението, както и няколко решения на колеги от предишни издания на курса в GitHub, и забелязах, че всички подхождат по аналогичен начин към проблема и използват алгоритъм с квадратична сложност за решаване на задачата.

Това е решението от упражнението:

Може да е заради желанието непременно да се използва опашка, но все пак реших да споделя и едно решение с масив, което е с линейна сложност.

Разликите в бързодействието са огромни и над определен брой елементи наивното (квадратично) решение практически спира да работи.

20000 + 2 елемента:

Number of elements (fuel pumps): 20002

Linear Algorithm (array)...
Elapsed time in milliseconds: 6
Counter: 60003
Start index: 20001

Quadratic Algorithm (queue)...
Elapsed time in milliseconds: 1881
Counter: 200050003
Start index: 20001

50000 + 2 елемента:

Number of elements (fuel pumps): 50002

Linear Algorithm (array)...
Elapsed time in milliseconds: 12
Counter: 150003
Start index: 50001

Quadratic Algorithm (queue)...
Elapsed time in milliseconds: 15763
Counter: 1250125003
Start index: 50001

Надявам се този пост да събуди интереса на повече колеги към алгоритмите и намирането на ефективни решения, а също и да вдигне малко нивото на курса...