Как оптимизировать алгоритм?

Question

[DenisVladimirovich]

Доброго времени суток, друзья, решил я тут поупражняться и прошел тест на Codility по поводу пересечения дисков. Решил я его на 93%, но большинство кто его просят проходить, требуют 100%.

using System;
class Solution {
    public int solution(int[] A) {
        int count = A.Length;
            int[] rangeMin = new int[count];
            int[] rangeMax = new int[count];
            for (int i=0; i<count; i++)
            {
                rangeMin[i] = i - A[i];
                rangeMax[i] = i + A[i];
            }
            Array.Sort(rangeMax);
            Array.Sort(rangeMin);

            int lower = 0;
            int intersections = 0;
            for(int k=0;k<count; k++)
            {
                while ((lower < count) && (rangeMax[k] >= rangeMin[lower])){
                    lower++;
                }

                intersections += lower - k - 1;
                if (intersections > 10000000)
                    return -1;

            }
            return intersections;
    }
}

Подскажите как можно оптимизировать данный код?
Ссылка на результат теста

Comments

[GavriKos]

Без пруфов, поэтому в комментариях. Мне кажется не нужны две сортировки. Можно обойтись сортировкой исходного массива А, и потом сразу хитро заполнять range.

Answer 1

[Rsa97]

У вас же в задаче сказано, что A[i] может равняться MAXINT. Естественно, при добавлении i вы выходите за пределы целочисленного типа.
Но, вам известно, что N не может быть больше 100000. Значит анализировать дальше этой границы смысла не имеет.
rangeMax[i] = A[i] > 100000 ? 100001 : i + A[i];