c# - 如何确定给定范围内的最佳间隔计数？

Question

我正在尝试确定这个棘手问题的最佳解决方案。我有一个长度(比方说 11)。所以这是一个0-10的一维空间。现在，我得到了这些具有相同 长度的间隔(在此示例中假设为 2)。现在它们是随机分布的(重叠或不重叠)。让我举个例子:

Situation:

|00|01|02|03|04|05|06|07|08|09|10| <- Space (length = 11)

|-----|       
         |-----|
            |-----|
               |-----|
                  |-----|
                           |-----| <- single interval of length = 2

现在，解决方案需要找到一次可以不重叠的最大间隔数。

The solution is: 4 intervals

4个区间有3个结果:

|00|01|02|03|04|05|06|07|08|09|10|

|-----|  |-----|-----|     |-----| <- result 1
|-----|  |-----|  |-----|  |-----| <- result 2
|-----|     |-----|-----|  |-----| <- result 3

但是还有两个约束。

1. 如果有更多结果(最佳解决方案，在本例中 = 4)，则选择间隔最少的结果。

2. 如果有更多结果，仍然是所有空格中最小长度最大的结果。例如，带有(长度)2 和 3 的空格的最小空格长度 = 2，这优于 1 和 4，其中最小空格长度仅为 1。

所以结果 2 有 4 个“连续” block ，另外两个只有 3 个，所以细化是:

|00|01|02|03|04|05|06|07|08|09|10|

|-----|  |-----------|     |-----| <- result 1
|-----|     |-----------|  |-----| <- result 3

这两个之间的空间分布相同，所以让我们看第一个。

输入集的结果是:

Interval count  : 4
Optimal solution: |-----|  |-----------|     |-----|

该算法必须适用于所有空间长度(不仅是 11)、所有间隔长度(间隔长度始终 <= 空间长度)和任意数量的间隔。

更新:

有问题的场景:

|00|01|02|03|04|05|06|07|08|09|

|-----|  
         |-----| 
            |-----|     
                        |-----|
|-----|

Answer 1

这是一个简单的动态规划问题。

令总长度为N，任务长度为L。

设F(T)为子区间(T, N)中可以选择的最大任务数，则在每个单位时间T，有3 种可能性:

1. 没有从 T 开始的任务。
2. 有一个从 T 开始的任务，但我们不将其包含在结果集中。
3. 有一个从 T 开始的任务，我们确实将其包含在结果集中。

情况 1 很简单，我们只有 F(T) = F(T + 1)。

在情况 2/3 中，请注意选择一个启动 T 的任务意味着我们必须拒绝所有在该任务运行时启动的任务，即在 T 和T + L。所以我们得到 F(T) = max(F(T + 1), F(T + L) + 1)。

最后，F(N) = 0。因此，您只需从 F(N) 开始，然后返回到 F(0)。

编辑:这将为您提供最大间隔数，但不是满足您的 2 个约束的集合。我不清楚你对限制的解释，所以我不确定如何帮助你。特别是，我不知道约束 1 是什么意思，因为您的示例集的所有解决方案显然都是相等的。

编辑 2:根据要求进一步解释:

考虑您发布的示例，我们有 N = 11 和 L = 2。有些任务从 T = 0, 3, 4, 5, 6, 9 开始。从 F(11) = 0 开始并向后计算:

• F(11) = 0
• F(10) = F(11) = 0(因为没有任务从 T = 10 开始)
• F(9) = max(F(10), F(11) + 1) = 1
• ...

最终我们得到 F(0) = 4:

T   |00|01|02|03|04|05|06|07|08|09|10|
F(T)| 4| 3| 3| 3| 3| 2| 2| 1| 1| 1| 0|

编辑 3: 好吧，我对此很好奇，所以我写了一个解决方案，所以不妨将其发布。这将为您提供具有最多任务、最少间隙数和最小最小间隙的集合。问题中示例的输出是:

• (0, 2) -> (4, 6) -> (6, 8) -> (9, 11)
• (0, 2) -> (4, 6) -> (8, 10)

显然，我不保证正确性! :)

私有(private)类任务 { 公共(public) int 开始 { 得到;放; } 公共(public) int 长度 { 得到;放; } public int End { get { return Start + Length; }

    public override string ToString()
    {
        return string.Format("({0:d}, {1:d})", Start, End);
    }
}

private class CacheEntry : IComparable
{
    public int Tasks { get; set; }
    public int Gaps { get; set; }
    public int MinGap { get; set; }
    public Task Task { get; set; }
    public Task NextTask { get; set; }

    public int CompareTo(object obj)
    {
        var other = obj as CacheEntry;
        if (Tasks != other.Tasks)
            return Tasks - other.Tasks; // More tasks is better
        if (Gaps != other.Gaps)
            return other.Gaps = Gaps; // Less gaps is better
        return MinGap - other.MinGap; // Larger minimum gap is better
    }
}

private static IList<Task> F(IList<Task> tasks)
{
    var end = tasks.Max(x => x.End);
    var tasksByTime = tasks.ToLookup(x => x.Start);
    var cache = new List<CacheEntry>[end + 1];

    cache[end] = new List<CacheEntry> { new CacheEntry { Tasks = 0, Gaps = 0, MinGap = end + 1 } };

    for (int t = end - 1; t >= 0; t--)
    {
        if (!tasksByTime.Contains(t))
        {
            cache[t] = cache[t + 1];
            continue;
        }

        foreach (var task in tasksByTime[t])
        {
            var oldCEs = cache[t + task.Length];
            var firstOldCE = oldCEs.First();
            var lastOldCE = oldCEs.Last();

            var newCE = new CacheEntry
            {
                Tasks = firstOldCE.Tasks + 1,
                Task = task,
                Gaps = firstOldCE.Gaps,
                MinGap = firstOldCE.MinGap
            };

            // If there is a task that starts at time T + L, then that will always 
            // be the best option for us, as it will have one less Gap than the others
            if (firstOldCE.Task == null || firstOldCE.Task.Start == task.End)
            {
                newCE.NextTask = firstOldCE.Task;
            }
            // Otherwise we want the one that maximises MinGap.
            else
            {
                var ce = oldCEs.OrderBy(x => Math.Min(x.Task.Start - newCE.Task.End, x.MinGap)).Last();
                newCE.NextTask = ce.Task;
                newCE.Gaps++;
                newCE.MinGap = Math.Min(ce.MinGap, ce.Task.Start - task.End);
            }

            var toComp = cache[t] ?? cache[t + 1];
            if (newCE.CompareTo(toComp.First()) < 0)
            {
                cache[t] = toComp;
            }
            else
            {
                var ceList = new List<CacheEntry> { newCE };

                // We need to keep track of all subsolutions X that start on the interval [T, T+L] that
                // have an equal number of tasks and gaps, but a possibly a smaller MinGap. This is
                // because an earlier task may have an even smaller gap to this task.
                int idx = newCE.Task.Start + 1;
                while (idx < newCE.Task.End)
                {
                    toComp = cache[idx];
                    if
                    (
                        newCE.Tasks == toComp.First().Tasks &&
                        newCE.Gaps == toComp.First().Gaps &&
                        newCE.MinGap >= toComp.First().MinGap
                    )
                    {
                        ceList.AddRange(toComp);
                        idx += toComp.First().Task.End;
                    }
                    else
                        idx++;
                }

                cache[t] = ceList;
            }
        }
    }

    var rv = new List<Task>();
    var curr = cache[0].First();
    while (true)
    {
        rv.Add(curr.Task);
        if (curr.NextTask == null) break;
        curr = cache[curr.NextTask.Start].First();
    }

    return rv;
}

public static void Main()
{
    IList<Task> tasks, sol;

    tasks = new List<Task>
    {
        new Task { Start = 0, Length = 2 },
        new Task { Start = 3, Length = 2 },
        new Task { Start = 4, Length = 2 },
        new Task { Start = 5, Length = 2 },
        new Task { Start = 6, Length = 2 },
        new Task { Start = 9, Length = 2 },
    };

    sol = F(tasks);
    foreach (var task in sol)
        Console.Out.WriteLine(task);
    Console.Out.WriteLine();

    tasks = new List<Task>
    {
        new Task { Start = 0, Length = 2 },
        new Task { Start = 3, Length = 2 },
        new Task { Start = 4, Length = 2 },
        new Task { Start = 8, Length = 2 },
    };

    sol = F(tasks);
    foreach (var task in sol)
        Console.Out.WriteLine(task);
    Console.Out.WriteLine();

    tasks = new List<Task>
    {
        new Task { Start = 0, Length = 5 },
        new Task { Start = 6, Length = 5 },
        new Task { Start = 7, Length = 3 },
        new Task { Start = 8, Length = 9 },
        new Task { Start = 19, Length = 1 },
    };

    sol = F(tasks);
    foreach (var task in sol)
        Console.Out.WriteLine(task);
    Console.Out.WriteLine();

    Console.In.ReadLine();
}