这是一个我很困惑的编码问题。
给定一个二维数组[[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。
我应该对这样的问题应用什么算法?我猜这是区间调度的变体问题?
谢谢
我希望我能正确理解这个问题。这是我能用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;
}
}
我认为你可以使用扫描算法解决这个问题。这是我的方法:
一般的想法是,我们将找到必须删除的最小间隔数,以便使所有数字都符合限制,而不是找出您可以选择且仍然符合限制的最大间隔数。以下是我们如何做到这一点:
首先创建三元组的向量,第一部分是整数,第二部分是布尔值,第三部分是整数。第一部分代表输入中的所有数字(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
。该组应按递增顺序排序。
迭代向量时,我们可能会遇到以下两种可能之一:
start
。在这种情况下,我们只需将此区间的end
(由第三部分id
标识)添加到集合中。如果集合的大小超过限制,我们必须确切地删除一个间隔,但哪个间隔最适合删除?当然,这是end
最大的区间,因为删除这个区间不仅可以帮助你减少所需的间隔数量以适应极限,但是它将在未来最有用,因为它持续时间最长。只需从集合中删除此间隔(相应的end
将在集合中的最后一个,因为集合按照end
的递增顺序排序)end
,在这种情况下检查一下。如果它包含指定的end
,只需删除它,因为相应的间隔已经结束。如果该集合不包含与我们正在处理的end
匹配的end
,则只需继续迭代到下一个元素,因为这意味着我们已经决定不采用相应的间隔。如果您需要计算拍摄间隔的数量,甚至打印它们,可以轻松完成。每当你处理一个区间的end
时,你实际上在该组中找到了这个qazxswpoi,这意味着相应的区间是一个,你可以将你的答案增加一个,打印它或保存在代表你的答案的某个向量中。
我的方法的总复杂度是:N Log(N),其中N是输入中给出的区间数。