algorithm - 不超过覆盖范围限制的最大间隔子集？

Question

这是一个令我感到困惑的编码问题。

给定一个二维数组 [[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;
            }
        }