Максимальные подмножества интервалов, которые не превышают лимит покрытия?

Question

Вот один кодовый вопрос, который меня смущает.

Учитывая 2-D массив [[1, 9], [2, 8], [2, 5], [3, 4], [6, 7], [6, 8]]каждый внутренний массив представляет интервал; и если мы соберем эти интервалы, мы увидим:

1 2 3 4 5 6 7 8 9
  2 3 4 5 6 7 8
  2 3 4 5 
    3 4   
          6 7
          6 7 8

Теперь есть предел, что покрытие должно быть <= 3 для каждой позиции; и, очевидно, мы могли видеть для позиций 3, 4, 6, 7, покрытие 4.

Тогда возникает вопрос: максимально, сколько подмножеств интервалов можно выбрать, чтобы каждый интервал мог соответствовать пределу <= 3? Совершенно очевидно, что в этом случае мы просто удаляем самый длинный интервал [1, 9], поэтому максимальное число подмножеств равно 6 - 1 = 5.

Какой алгоритм я должен применить к такому вопросу? Я думаю, что это вариант вопроса с интервалом планирования?

Спасибо

Answer 1

Надеюсь, я правильно понял вопрос. Это решение, которое я смог получить с помощью C#:

                //test
                int[][] grid =  { new int[]{ 1, 9 }, new int[] { 2, 8 }, new int[] { 2, 5 }, new int[] { 3, 4 }, new int[] { 6, 7 }, new int[] { 6, 8 } };
                SubsetFinder sf = new SubsetFinder(grid);
                int t1 = sf.GetNumberOfIntervals(1);//6
                int t2 = sf.GetNumberOfIntervals(2);//5
                int t3 = sf.GetNumberOfIntervals(3);//5
                int t4 = sf.GetNumberOfIntervals(4);//2
                int t5 = sf.GetNumberOfIntervals(5);//0


        class SubsetFinder
        {
            Dictionary<int, List<int>> dic;
            int intervalCount;
            public SubsetFinder(int[][] grid)
            {
                init(grid);
            }
            private void init(int[][] grid)
            {
                this.dic = new Dictionary<int, List<int>>();
                this.intervalCount = grid.Length;
                for (int r = 0; r < grid.Length; r++)
                {
                    int[] row = grid[r];
                    if (row.Length != 2) throw new Exception("not grid");
                    int start = row[0];
                    int end = row[1];
                    if (end < start) throw new Exception("bad interval");
                    for (int i = start; i <= end; i++)
                        if (!dic.ContainsKey(i))
                            dic.Add(i, new List<int>(new int[] { r }));
                        else
                            dic[i].Add(r);
                }
            }
            public int GetNumberOfIntervals(int coverageLimit)
            {
                HashSet<int> hsExclude = new HashSet<int>();
                foreach (int key in dic.Keys)
                {
                    List<int> lst = dic[key];
                    if (lst.Count < coverageLimit)
                        foreach (int i in lst)
                            hsExclude.Add(i);
                }
                return intervalCount - hsExclude.Count;
            }
        }

Answer 2

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

Общая идея заключается в том, что вместо того, чтобы определить максимальное количество интервалов, которое вы можете выбрать и по-прежнему соответствовать пределу, мы найдем минимальное количество интервалов, которое необходимо удалить, чтобы все числа соответствовали пределу. Вот как мы можем это сделать:

Сначала создайте вектор троек, первая часть - целое число, вторая - логическое значение, а третья часть - целое число. Первая часть представляет все числа от входа (оба start а также end интервалов), вторая часть говорит нам, является ли первая часть началом или концом интервала, в то время как третья часть представляет id интервала.

Сортировать созданный вектор на основе первой части, в случае start должен прийти раньше end некоторых интервалов.

В приведенном вами примере вектор будет:

1,0, 2,0, 2,0, 2,0, 3,0, 4,1, 5,1, 6.0, 6.0, 7,1, 8,1, 8,1, 9,1

Теперь итерируем вектор, сохраняя набор целых чисел, которые представляют интервалы, которые в настоящее время взяты. Числа внутри набора представляют ends из принятых в настоящее время интервалов. Этот набор должен храниться в порядке возрастания.

Итерируя по вектору, мы можем столкнуться с одной из следующих 2 возможностей:

1. В настоящее время мы занимаемся start интервала. В этом случае мы просто добавляем end этого интервала (который определяется третьей частью id) к набору. Если размер набора больше предела, мы обязательно должны удалить ровно один интервал, но какой интервал лучше всего удалить? Конечно, это интервал с самым большим end потому что удаление этого интервала не только поможет вам уменьшить количество взятых интервалов, чтобы соответствовать пределу, но также будет наиболее полезным в будущем, так как он длится больше всего. Просто удалите этот интервал из набора (соответствующий end будет последним в наборе, так как набор отсортирован в порядке возрастания end)

2. В настоящее время мы занимаемся end интервала, в этом случае проверьте набор. Если он содержит указанное end, просто удалите его, потому что соответствующий интервал подошел к концу. Если набор не содержит end это соответствует тому, с которым мы работаем, просто продолжайте итерацию к следующему элементу, потому что это означает, что мы уже решили не брать соответствующий интервал.

Если вам нужно посчитать количество взятых интервалов или даже распечатать их, это можно сделать легко. Всякий раз, когда вы справляетесь с end интервала, и вы на самом деле найдете это end в данном случае это означает, что соответствующий интервал является взятым, и вы можете увеличить свой ответ на единицу, распечатать его или сохранить в каком-либо векторе, представляющем ваш ответ.

Общая сложность моего подхода: N Log (N), где N - количество интервалов, заданных на входе.