Алгоритм расчета количества пересекающихся дисков

Question

Учитывая массив A из N целых чисел, мы рисуем N диски в 2D-плоскости, так что i-й диск имеет центр в (0,i) и радиус A[i].Мы говорим, что k-й диск и j-й диск пересекаются, если k-й и j-й диски имеют хотя бы одну общую точку.

Напишите функцию

int number_of_disc_intersections(int[] A);

, которая с массивом A, описывающим диски N, как описано выше, возвращает количество пар пересекающихся дисков.Например, для N=6 и

A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0

существует 11 пар пересекающихся дисков:

0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th

, поэтому функция должна возвращать 11. Функция должна возвращать -1, если числопересекающихся пар превышает 10 000 000.Функция может предполагать, что N не превышает 10 000 000.

Answer 1

Реализация 100/100 C #, описанная Aryabhatta (решение для двоичного поиска).

using System;

class Solution {
    public int solution(int[] A)
    {
        return IntersectingDiscs.Execute(A);
    }
}

class IntersectingDiscs
{
    public static int Execute(int[] data)
    {
        int counter = 0;

        var intervals = Interval.GetIntervals(data);

        Array.Sort(intervals); // sort by Left value

        for (int i = 0; i < intervals.Length; i++)
        {
            counter += GetCoverage(intervals, i);

            if(counter > 10000000)
            {
                return -1;
            }
        }

        return counter;
    }

    private static int GetCoverage(Interval[] intervals, int i)
    {
        var currentInterval = intervals[i];

        // search for an interval starting at currentInterval.Right

        int j = Array.BinarySearch(intervals, new Interval { Left = currentInterval.Right });

        if(j < 0)
        {
            // item not found

            j = ~j; // bitwise complement (see Array.BinarySearch documentation)

            // now j == index of the next item larger than the searched one

            j = j - 1; // set index to the previous element
        }

        while(j + 1 < intervals.Length && intervals[j].Left == intervals[j + 1].Left)
        {
            j++; // get the rightmost interval starting from currentInterval.Righ
        }

        return j - i; // reduce already processed intervals (the left side from currentInterval)
    }
}

class Interval : IComparable
{
    public long Left { get; set; }
    public long Right { get; set; }

    // Implementation of IComparable interface
    // which is used by Array.Sort().
    public int CompareTo(object obj)
    {
        // elements will be sorted by Left value

        var another = obj as Interval;

        if (this.Left < another.Left)
        {
            return -1;
        }

        if (this.Left > another.Left)
        {
            return 1;
        }

        return 0;
    }

    /// <summary>
    /// Transform array items into Intervals (eg. {1, 2, 4} -> {[-1,1], [-1,3], [-2,6]}).
    /// </summary>
    public static Interval[] GetIntervals(int[] data)
    {
        var intervals = new Interval[data.Length];

        for (int i = 0; i < data.Length; i++)
        {
            // use long to avoid data overflow (eg. int.MaxValue + 1)

            long radius = data[i];

            intervals[i] = new Interval
            {
                Left = i - radius,
                Right = i + radius
            };
        }

        return intervals;
    }
}