我在约会中有多个“从时间”和“到时间”。例如：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 小时。我如何计算这道题的正确答案？
3 回答
温温酱
TA贡献1752条经验 获得超4个赞
这比您想象的要困难，至少对于一般情况来说是这样。
这是一个类的修改版本，我用于计算数字范围，考虑重叠区域（完整的类还处理排除的区域，我已将其包含在内，但未用于此答案）：
public sealed class RangeCombiner
{
public void Include(long start, long end)
{
_boundaries.Add(new Boundary(start, isStart: true, isIncluded: true));
_boundaries.Add(new Boundary(end, isStart: false, isIncluded: true));
_sorted = false;
}
public void Exclude(long start, long end)
{
_boundaries.Add(new Boundary(start, isStart: true, isIncluded: false));
_boundaries.Add(new Boundary(end, isStart: false, isIncluded: false));
_sorted = false;
}
public void Clear()
{
_boundaries.Clear();
}
public long TotalIncludedRange()
{
sortIfNecessary();
return totalIncludedRange();
}
void sortIfNecessary()
{
if (_sorted)
return;
_boundaries.Sort();
_sorted = true;
}
long totalIncludedRange()
{
int included = 0;
int excluded = 0;
long start = 0;
long total = 0;
for (int i = 0; i < _boundaries.Count; ++i)
{
if (_boundaries[i].IsStart) // Starting a region...
{
if (_boundaries[i].IsIncluded) // Starting an included region...
{
if (++included == 1 && excluded == 0) // Starting a new included region,
start = _boundaries[i].Value; // so remember its start time.
}
else // Starting an excluded region...
{
if (++excluded == 1 && included > 0) // Ending an included region,
total += _boundaries[i].Value - start; // so add its range to the total.
}
}
else // Ending a region...
{
if (_boundaries[i].IsIncluded) // Ending an included region...
{
if (--included == 0 && excluded == 0) // Ending an included region,
total += _boundaries[i].Value - start; // so add its range to the total.
}
else // Ending an excluded region...
{
if (--excluded == 0 && included > 0) // Starting an included region,
start = _boundaries[i].Value; // so remember its start time.
}
}
}
return total;
}
readonly List<Boundary> _boundaries = new List<Boundary>();
bool _sorted;
struct Boundary : IComparable<Boundary>
{
public Boundary(long value, bool isStart, bool isIncluded)
{
Value = value;
IsStart = isStart;
IsIncluded = isIncluded;
}
public int CompareTo(Boundary other)
{
if (this.Value < other.Value)
return -1;
if (this.Value > other.Value)
return 1;
if (this.IsStart == other.IsStart)
return 0;
if (this.IsStart)
return -1;
return 1;
}
public readonly long Value;
public readonly bool IsStart;
public readonly bool IsIncluded;
}
}
以下是如何使用它来解决您的问题。请注意我如何将DateTime值转换为区域的刻度计数：
以下代码的输出是Total = 09:00:00：
class Program
{
static void Main()
{
var combiner = new RangeCombiner();
var from1 = new DateTime(2019, 08, 07, 10, 00, 00);
var to1 = new DateTime(2019, 08, 07, 12, 00, 00);
var from2 = new DateTime(2019, 08, 07, 10, 00, 00);
var to2 = new DateTime(2019, 08, 07, 12, 00, 00);
var from3 = new DateTime(2019, 08, 07, 11, 00, 00);
var to3 = new DateTime(2019, 08, 07, 12, 00, 00);
var from4 = new DateTime(2019, 08, 07, 11, 00, 00);
var to4 = new DateTime(2019, 08, 07, 14, 00, 00);
var from5 = new DateTime(2019, 08, 07, 14, 00, 00);
var to5 = new DateTime(2019, 08, 07, 18, 00, 00);
var from6 = new DateTime(2019, 08, 07, 15, 00, 00);
var to6 = new DateTime(2019, 08, 07, 17, 00, 00);
var from7 = new DateTime(2019, 08, 07, 18, 00, 00);
var to7 = new DateTime(2019, 08, 07, 19, 00, 00);
combiner.Include(from1.Ticks, to1.Ticks);
combiner.Include(from2.Ticks, to2.Ticks);
combiner.Include(from3.Ticks, to3.Ticks);
combiner.Include(from4.Ticks, to4.Ticks);
combiner.Include(from5.Ticks, to5.Ticks);
combiner.Include(from6.Ticks, to6.Ticks);
combiner.Include(from7.Ticks, to7.Ticks);
Console.WriteLine("Total = " + TimeSpan.FromTicks(combiner.TotalIncludedRange()));
}
}
复杂：
添加数据是一个 O(N) 操作
计算总的非重叠非排除是 O(N.Log(N)) 操作。
因此相加计算总体也是O(N.Log(N))。
慕沐林林
TA贡献2016条经验 获得超9个赞
这将为您提供每一天的总小时数列表。
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
杨魅力
TA贡献1811条经验 获得超6个赞
考虑到 LINQ 的算法（请注意，我不编写 C#）：
有一个包含字段的类：totime、fromtime、date、差值计算字段。
为该类实现 equals 和 hash 方法
使用 LINQ 将集合从 DB 转换为 Set。-
HashSet<T> foo = new HashSet<T>(from x in bar.Items select x);变换设置回列表。
做一个聚合，将差异求和。
在我看来，如果没有 LINQ，事情会更容易。
- 3 回答
- 0 关注
- 132 浏览
添加回答
举报
0/150
提交
取消