我在約會中有多個“從時間”和“到時間”。例如：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條經(jīng)驗 獲得超4個贊
這比您想象的要困難，至少對于一般情況來說是這樣。
這是一個類的修改版本，我用于計算數(shù)字范圍，考慮重疊區(qū)域（完整的類還處理排除的區(qū)域，我已將其包含在內(nèi)，但未用于此答案）：
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值轉換為區(qū)域的刻度計數(shù)：
以下代碼的輸出是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()));
}
}
復雜：
添加數(shù)據(jù)是一個 O(N) 操作
計算總的非重疊非排除是 O(N.Log(N)) 操作。
因此相加計算總體也是O(N.Log(N))。
慕沐林林
TA貢獻2016條經(jīng)驗 獲得超9個贊
這將為您提供每一天的總小時數(shù)列表。
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 上午 營業(yè)時間：02:00:00
楊魅力
TA貢獻1811條經(jīng)驗 獲得超6個贊
考慮到 LINQ 的算法（請注意，我不編寫 C#）：
有一個包含字段的類：totime、fromtime、date、差值計算字段。
為該類實現(xiàn) equals 和 hash 方法
使用 LINQ 將集合從 DB 轉換為 Set。-
HashSet<T> foo = new HashSet<T>(from x in bar.Items select x);變換設置回列表。
做一個聚合，將差異求和。
在我看來，如果沒有 LINQ，事情會更容易。
- 3 回答
- 0 關注
- 167 瀏覽
添加回答
舉報
0/150
提交
取消