2

我有以下问题，最好用图表来描述：考虑以下序列（可以是任何类型的序列：数字、日期（在我的情况下是日期）等）

图表

我想找到最长连续序列的所有组，如后一个示例中的输出，即包含可能最长序列的组的最少数量。

我想过进行某种排序/排序（最小/最大在这里似乎没有太大帮助，因为我可能有空白），首先是左点，然后是右点，但我不确定任何一个。

4

4 回答 4

4

我会将起点和终点一起排序为一个排序顺序，然后按该顺序处理它们，保持看到的起点数减去看到的终点数的连续计数。当此计数器降至零时，您将开始一个完整的间隙。根据邻接线是否算作由零长度间隙分隔，您可以在连接的情况下在端点之前或之后对起点进行排序。

于 2013-07-31T19:17:36.737 回答
3

只是从我上次编写这样的代码时吐出一些伪代码：

var outputRanges = new List<Range>();
foreach (var range in inputRanges)
{
   // Let Range.Touches(Range) define a function that returns true
   // iff the two ranges overlap at all (that is, A.Start and/or A.End
   // is between B.Start and B.End)
   var overlaps = outputRanges.Where(range.Touches).ToList();

   // If there are no overlaps, then simply add it to the output
   if (!overlaps.Any())
   {
       outputRanges.Add(range);
   }
   // If there are overlaps, merge them
   else
   {
       outputRanges.RemoveAll(overlaps);
       overlaps.Add(range);
       outputRange.Add(new Range() {
           Start = overlaps.Min(_=>_.Start),
           End = overlaps.Max(_=>_.End)
       });
   }
}
于 2013-07-31T19:23:18.207 回答
0

我在 C# 中没有它，但确实必须在 sql 中解决这个确切的问题，也许这会给你一个提示，告诉你如何把它变成 C#

select Resource_ID, Appointment_date, Min(NewStartTime) Start_Time, MAX(End_Time) End_Time
into #CleanedBlockTimes
from
(
    select *,
        NewStartTime = Dateadd(mi, v.number, t.Start_Time),
        NewStartTimeGroup =
            dateadd(mi,
                    1- DENSE_RANK() over (partition by Resource_ID, Appointment_date order by Dateadd(mi, v.number, t.Start_Time)),
                    Dateadd(mi, v.number, t.Start_Time))
    from #BlockTimes t
    inner join master..spt_values v
      on v.type='P' and v.number <= DATEDIFF(mi, Start_Time, End_Time)
) X
group by Resource_ID, Appointment_date, NewStartTimeGroup
order by Resource_ID, Appointment_date, Start_Time
于 2013-07-31T19:20:17.733 回答
0

在范围的开头排序。

从列表的头部开始，将结束时间与列表中下一项的开始时间进行比较。如果它们重叠，则将结束时间替换为当前记录的结束时间和下一条记录的结束时间的最大值。删除下一条记录。重复。

如果没有重叠，则前进到下一条记录并重复。

O(n log n) 用于排序，O(n) 用于编译。总体而言，o(n log n)。

于 2013-07-31T21:57:13.063 回答