如何计算具有相似时间跨度的一天中的时间跨度总和

Question

我在约会中有多个“从时间”和“到时间”。

例如：

from time    | - to Time -     |---- Date ---- | -- diff date -- 

 -- 10:00 -- |   -- 12:00 --   |  2019-08-07   |      2 Hours

 -- 10:00 -- |   -- 12:00 --   |  2019-08-07   |      2 Hours

 -- 11:00 -- |   -- 12:00 --   |  2019-08-07   |      1 Hours

 -- 11:00 -- |   -- 14:00 --   |  2019-08-07   |      3 Hours

 -- 14:00 -- |   -- 18:00 --   |  2019-08-07   |      4 Hours

 -- 15:00 -- |   -- 17:00 --   |  2019-08-07   |      2 Hours

 -- 18:00 -- |   -- 19:00 --   |  2019-08-07   |      1 Hours

上述时间总和为：15 小时

但它是错误的。因为有些时候是重复的。正确答案是 9 小时。

我如何计算这道题的正确答案？

Answer 1

这比您想象的要困难，至少对于一般情况来说是这样。这是一个类的修改版本，我用于计算数字范围，考虑重叠区域（完整的类还处理排除的区域，我已将其包含在内，但未用于此答案）：public sealed class RangeCombiner{&nbsp; &nbsp; public void Include(long start, long end)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; _boundaries.Add(new Boundary(start, isStart: true, isIncluded: true));&nbsp; &nbsp; &nbsp; &nbsp; _boundaries.Add(new Boundary(end, isStart: false, isIncluded: true));&nbsp; &nbsp; &nbsp; &nbsp; _sorted = false;&nbsp; &nbsp; }&nbsp; &nbsp; public void Exclude(long start, long end)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; _boundaries.Add(new Boundary(start, isStart: true, isIncluded: false));&nbsp; &nbsp; &nbsp; &nbsp; _boundaries.Add(new Boundary(end, isStart: false, isIncluded: false));&nbsp; &nbsp; &nbsp; &nbsp; _sorted = false;&nbsp; &nbsp; }&nbsp; &nbsp; public void Clear()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; _boundaries.Clear();&nbsp; &nbsp; }&nbsp; &nbsp; public long TotalIncludedRange()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; sortIfNecessary();&nbsp; &nbsp; &nbsp; &nbsp; return totalIncludedRange();&nbsp; &nbsp; }&nbsp; &nbsp; void sortIfNecessary()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if (_sorted)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; _boundaries.Sort();&nbsp; &nbsp; &nbsp; &nbsp; _sorted = true;&nbsp; &nbsp; }&nbsp; &nbsp; long totalIncludedRange()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int&nbsp; included = 0;&nbsp; &nbsp; &nbsp; &nbsp; int&nbsp; excluded = 0;&nbsp; &nbsp; &nbsp; &nbsp; long start&nbsp; &nbsp; = 0;&nbsp; &nbsp; &nbsp; &nbsp; long total&nbsp; &nbsp; = 0;&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < _boundaries.Count; ++i)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (_boundaries[i].IsStart)&nbsp; &nbsp; &nbsp;// Starting a region...&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (_boundaries[i].IsIncluded)&nbsp; &nbsp; &nbsp; // Starting an included region...&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (++included == 1 && excluded == 0)&nbsp; &nbsp; &nbsp; &nbsp;// Starting a new included region,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = _boundaries[i].Value;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // so remember its start time.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Starting an excluded region...&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (++excluded == 1 && included > 0)&nbsp; &nbsp; &nbsp; &nbsp; // Ending an included region,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total += _boundaries[i].Value - start;&nbsp; &nbsp;// so add its range to the total.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Ending a region...&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (_boundaries[i].IsIncluded)&nbsp; &nbsp; &nbsp; // Ending an included region...&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (--included == 0 && excluded == 0)&nbsp; &nbsp; &nbsp; &nbsp;// Ending an included region,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total += _boundaries[i].Value - start;&nbsp; &nbsp;// so add its range to the total.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Ending an excluded region...&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (--excluded == 0 && included > 0)&nbsp; &nbsp; &nbsp; &nbsp; // Starting an included region,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = _boundaries[i].Value;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // so remember its start time.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return total;&nbsp; &nbsp; }&nbsp; &nbsp; readonly List<Boundary> _boundaries = new List<Boundary>();&nbsp; &nbsp; bool _sorted;&nbsp; &nbsp; struct Boundary : IComparable<Boundary>&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; public Boundary(long value, bool isStart, bool isIncluded)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Value&nbsp; &nbsp; &nbsp; = value;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; IsStart&nbsp; &nbsp; = isStart;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; IsIncluded = isIncluded;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public int CompareTo(Boundary other)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (this.Value < other.Value)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return -1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (this.Value > other.Value)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (this.IsStart == other.IsStart)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (this.IsStart)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return -1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public readonly long Value;&nbsp; &nbsp; &nbsp; &nbsp; public readonly bool IsStart;&nbsp; &nbsp; &nbsp; &nbsp; public readonly bool IsIncluded;&nbsp; &nbsp; }}以下是如何使用它来解决您的问题。请注意我如何将DateTime值转换为区域的刻度计数：以下代码的输出是Total = 09:00:00：class Program{&nbsp; &nbsp; static void Main()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; var combiner = new RangeCombiner();&nbsp; &nbsp; &nbsp; &nbsp; var from1 = new DateTime(2019, 08, 07, 10, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var to1&nbsp; &nbsp;= new DateTime(2019, 08, 07, 12, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var from2 = new DateTime(2019, 08, 07, 10, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var to2&nbsp; &nbsp;= new DateTime(2019, 08, 07, 12, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var from3 = new DateTime(2019, 08, 07, 11, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var to3&nbsp; &nbsp;= new DateTime(2019, 08, 07, 12, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var from4 = new DateTime(2019, 08, 07, 11, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var to4&nbsp; &nbsp;= new DateTime(2019, 08, 07, 14, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var from5 = new DateTime(2019, 08, 07, 14, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var to5&nbsp; &nbsp;= new DateTime(2019, 08, 07, 18, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var from6 = new DateTime(2019, 08, 07, 15, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var to6&nbsp; &nbsp;= new DateTime(2019, 08, 07, 17, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var from7 = new DateTime(2019, 08, 07, 18, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; var to7&nbsp; &nbsp;= new DateTime(2019, 08, 07, 19, 00, 00);&nbsp; &nbsp; &nbsp; &nbsp; combiner.Include(from1.Ticks, to1.Ticks);&nbsp; &nbsp; &nbsp; &nbsp; combiner.Include(from2.Ticks, to2.Ticks);&nbsp; &nbsp; &nbsp; &nbsp; combiner.Include(from3.Ticks, to3.Ticks);&nbsp; &nbsp; &nbsp; &nbsp; combiner.Include(from4.Ticks, to4.Ticks);&nbsp; &nbsp; &nbsp; &nbsp; combiner.Include(from5.Ticks, to5.Ticks);&nbsp; &nbsp; &nbsp; &nbsp; combiner.Include(from6.Ticks, to6.Ticks);&nbsp; &nbsp; &nbsp; &nbsp; combiner.Include(from7.Ticks, to7.Ticks);&nbsp; &nbsp; &nbsp; &nbsp; Console.WriteLine("Total = " + TimeSpan.FromTicks(combiner.TotalIncludedRange()));&nbsp; &nbsp; }}复杂：添加数据是一个 O(N) 操作计算总的非重叠非排除是 O(N.Log(N)) 操作。因此相加计算总体也是O(N.Log(N))。

Answer 2

这将为您提供每一天的总小时数列表。List<DateTime> dates = new List<DateTime>(){    new DateTime(2019,1,1,10,0,0),    new DateTime(2019,1,1,12,0,0),    new DateTime(2019,1,1,13,0,0),    new DateTime(2019,1,1,14,0,0),    new DateTime(2019,1,2,10,0,0),    new DateTime(2019,1,2,12,0,0),    new DateTime(2019,1,2,14,0,0),    new DateTime(2019,1,3,10,0,0),    new DateTime(2019,1,3,11,0,0),    new DateTime(2019,1,3,12,0,0)   };  var result = dates    .OrderBy(d => d.Date)    .ThenBy(d => d.TimeOfDay)    .GroupBy(d => d.Date)    .Select(bla => new    {      Date = bla.First().Date,      Hours = bla.Last() - bla.First()    }).ToList();结果：日期：2019/1/1 12:00:00 AM 时间：04:00:00 日期：2019/1/2 12:00:00 AM 时间：04:00:00日期：2019/1/3 12:00 :00 上午 营业时间：02:00:00

Answer 3

考虑到 LINQ 的算法（请注意，我不编写 C#）：有一个包含字段的类：totime、fromtime、date、差值计算字段。为该类实现 equals 和 hash 方法使用 LINQ 将集合从 DB 转换为 Set。-&nbsp;HashSet<T> foo = new HashSet<T>(from x in bar.Items select x);变换设置回列表。做一个聚合，将差异求和。在我看来，如果没有 LINQ，事情会更容易。