Есть множество временных отрезков. Требуется вычислить процент покрытия этими отрезками другого временного отрезка Х. Началом Х является начало отрезка, начавшегося раньше всех других, а концом - конец отрезка, закончившегося позднее всех других.
Например:
Множество содержит отрезки A(0, 5) B(2, 6) C(9, 10)
Раньше всех начинается A, позднее всех заканчивается C. Т.е. процент покрытия должен быть вычислен для отрезка (0, 10).
Объединение отрезков A, B и C дает в сумме 7. Т.е. процент покрытия равен 70%.
В идеале мне нужен интерфейс на JAVA, в котором один метод позволял бы добавлять отрезки во множество а другой возвращал бы процент покрытия.
Интуиция подсказывает, что это уже должно быть когда-то и кем-то реализовано. Может кто-то наталкивался на что-то подобное? Спасибо заранее.

И что тебя останавливает? Там от силы на пару часов писанины.
Чтобы не делать двойной цикл - сделай дополнительный массивчик
и пересчитывай в нем каждый новый отрезок.
ЗЫ. А задачка в целых числах? Там можно и проще - заполнением...

Делов на 5 минут. Не тестировал, не на JAVA, но доработать наверняка сможешь и сам.

    public class Foo
    {
        List<int> intervals = new List<int>();
        public double AddInterval(int x1, int x2)
        {
            // merge intervals
            List<int> newIntervals = new List<int>();
            int j = 0;
            while (j < intervals.Count && intervals[j] < x1)
            {
                newIntervals.Add(intervals[j++]);
            }
            if (j == intervals.Count)
            {
                newIntervals.Add(x1);
            }
            else if ((j & 1) == 0)
            {
                newIntervals.Add(x1);
            }
            else if (intervals[j] == x1)
            {
                j++;
            }
            while (j < intervals.Count && intervals[j] < x2)
            {
                j++;
            }
            if (j == intervals.Count)
            {
                newIntervals.Add(x2);
            }
            else if (intervals[j] == x2)
            {
                if ((j & 1) == 0)
                {
                    j++;
                }
            }
            else if ((j & 1) == 0)
            {
                newIntervals.Add(x2);
            }
            while (j < intervals.Count)
            {
                newIntervals.Add(intervals[j++]);
            }
            
            intervals = newIntervals;

            // compute coverage                
            int totalLength = intervals[intervals.Count - 1] - intervals[0];
            int covered = 0;
            for (j = 0; j < intervals.Count; j += 2)
            {
                covered += intervals[j + 1] - intervals[j];
            }
            return ((double)covered) / totalLength;
        }
    }

Это на латыни наверно написано?

Спасибо за код. Переписал на JAVA. Вычисляет правильно. Единственное только, не знаю как в C# (это ведь на C#?), а в JAVA при повторном добавлении интервала, падает с исключением.

Переделал. Теперь должно работать.

Спасибо. Добавил еще кое какой код для себя. Теперь все работает как мне и нужно. А у меня что-то не получилось эту задачку за 5 минут решить. Поэтому собственно и создал тему.