代码之家  ›  专栏  ›  技术社区  ›  LookIntoEast

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

  •  4
  • LookIntoEast  · 技术社区  · 7 年前

    这里有一个我很困惑的编码问题。

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

    我应该用什么算法来解决这个问题?我想这是一个与时间间隔安排不同的问题?

    谢谢

    2 回复  |  直到 7 年前
        1
  •  1
  •   Koray    7 年前

    我希望我正确理解了这个问题。这是我用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;
                }
            }
    
        2
  •  1
  •   Said A. Sryheni    7 年前

    我想你可以用扫描算法来解决这个问题。我的方法如下:

    一般的想法是,我们将找到必须删除的最小间隔数,以使所有数字都符合限制,而不是找出您可以选择并仍符合限制的最大间隔数。我们可以这样做:

    首先创建一个三元组向量,第一部分是整数,第二部分是布尔值,而第三部分是整数。第一部分表示输入中的所有数字(包括 start end 第二部分告诉我们第一部分是间隔的开始还是结束,而第三部分代表 id 时间间隔的。

    根据第一部分对创建的向量进行排序,如果是平局 开始 应该在 终止 某些时间间隔。

    在您提供的示例中,向量将为:

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

    现在,在向量上迭代,同时保留一组整数,这些整数表示当前采用的间隔。集合中的数字表示 ends 当前采取的间隔。此集合应按递增顺序排序。

    在向量上迭代时,我们可能会遇到以下两种可能性之一:

    1. 我们目前正在处理 开始 间隔的。在这种情况下,我们只需添加 终止 该间隔(由第三部分确定 身份证件 )到集合。如果集合的大小超过了限制,我们必须只删除一个区间,但哪个区间最适合删除?当然这是间隔时间最大的 终止 因为删除此间隔不仅有助于减少所采取间隔的数量以满足限制,而且在将来也会非常有用,因为它持续时间最长。只需从集合中删除此间隔(对应的 终止 将是集合中的最后一个,因为集合按 终止 )

    2. 我们目前正在处理 终止 在这种情况下,请检查集合。如果包含指定的 终止 ,只需删除它,因为相应的间隔已经结束。如果集合不包含 终止 这与我们正在处理的元素相匹配,只需继续迭代到下一个元素,因为这意味着我们已经决定不采用相应的间隔。

    如果您需要计算所采取的间隔的数量,甚至需要打印它们,这很容易做到。无论何时处理 终止 你会发现 终止 在集合中,这意味着相应的间隔是一个已取的间隔,您可以将答案增加一,打印它或将其保存在表示您的答案的向量中。

    我的方法的总体复杂性是: N日志(N) 哪里 N 是输入中给定的间隔数。