查找最长重叠周期

与原始解决方案一样,您需要将每个间隔与其他间隔进行比较, 除了 间隔具有相同的id,因此我将这样编码:

支持类,只是为了简化实际算法:

class Period {
    public DateTime Start { get; }
    public DateTime End { get; }

    public Period(DateTime start, DateTime end) {
        this.Start = start;
        this.End = end;
    }

    public int Overlap(Period other) {
        DateTime a = this.Start > other.Start ? this.Start : other.Start;
        DateTime b = this.End < other.End ? this.End : other.End;
        return (a < b) ? b.Subtract(a).Days : 0;
    }
}

class IdData {
    public IdData() {
        this.Periods = new List<Period>();
        this.Overlaps = new Dictionary<int, int>();
    }
    public List<Period> Periods { get; }
    public Dictionary<int, int> Overlaps { get; }
}

查找最大重叠的方法:

    static int GetLongestElapsedPeriod(List<(int, DateTime, DateTime)> periods) {
        int maxOverlap = 0;

        Dictionary<int, IdData> ids = new Dictionary<int, IdData>();
        foreach (var period in periods) {
            int id = period.Item1;
            Period idPeriod = new Period(period.Item2, period.Item3);

            // preserve interval for ID
            var idData = ids.GetValueOrDefault(id, new IdData());
            idData.Periods.Add(idPeriod);
            ids[id] = idData;

            foreach (var idObj in ids) {
                if (idObj.Key != id) {
                    // here we calculate of new interval with all previously met
                    int o = idObj.Value.Overlaps.GetValueOrDefault(id, 0);
                    foreach (var otherPeriods in idObj.Value.Periods)
                        o += idPeriod.Overlap(otherPeriods);
                    idObj.Value.Overlaps[id] = o;

                    // check whether newly calculate overlapping is the maximal one, preserve Ids if needed too
                    if (o > maxOverlap)
                        maxOverlap = o;
                }
            }
        }

        return maxOverlap;
    }

您可以使用 TimePeriodLibrary。净额 :

PM>安装软件包TimePeriodLibrary。净额

TimePeriodCollection timePeriods = new TimePeriodCollection(
    data.Select(q => new TimeRange(q.Item2, q.Item3)));

var longestOverlap = timePeriods
    .OverlapPeriods(new TimeRange(timePeriods.Start, timePeriods.End))
    .OrderByDescending(q => q.Duration)
    .FirstOrDefault();

使用扩展方法:

public static T MaxBy<T, TKey>(this IEnumerable<T> src, Func<T, TKey> key, Comparer<TKey> keyComparer = null) {
    keyComparer = keyComparer ?? Comparer<TKey>.Default;
    return src.Aggregate((a, b) => keyComparer.Compare(key(a), key(b)) > 0 ? a : b);
}

和一些辅助函数

DateTime Max(DateTime a, DateTime b) => (a > b) ? a : b;
DateTime Min(DateTime a, DateTime b) => (a < b) ? a : b;

int OverlappingDays((DateTime DateFrom, DateTime DateTo) span1, (DateTime DateFrom, DateTime DateTo) span2) {
    var maxFrom = Max(span1.DateFrom, span2.DateFrom);
    var minTo = Min(span1.DateTo, span2.DateTo);
    return Math.Max((minTo - maxFrom).Days, 0);
}

可以将跨度与匹配的 Id s

var dg = data.GroupBy(d => d.Id);

生成所有对 身份证件 s

var pdgs = from d1 in dg
           from d2 in dg.Where(d => d.Key > d1.Key)
           select new[] { d1, d2 };

然后计算每对 身份证件 s并找到最大值:

var MaxOverlappingPair = pdgs.Select(pdg => new {
    Id1 = pdg[0].Key,
    Id2 = pdg[1].Key,
    OverlapInDays = pdg[0].SelectMany(d1 => pdg[1].Select(d2 => OverlappingDays((d1.DateFrom, d1.DateTo), (d2.DateFrom, d2.DateTo)))).Sum()
}).MaxBy(TwoOverlap => TwoOverlap.OverlapInDays);

既然提到了效率,我应该说直接实现其中一些操作而不是使用LINQ效率更高,但您使用的是元组和内存结构,所以我认为这不会有多大区别。

我使用24000个跨度和1249个唯一ID的列表运行了一些性能测试。LINQ代码耗时约16秒。通过内联一些LINQ并用元组替换匿名对象,时间降到了3.1秒左右。通过添加一个快捷方式,跳过任何累计天数小于当前最大重叠天数的ID,并进行一些优化,我将其缩短到1秒以内。

var baseDate = new DateTime(1970, 1, 1);

int OverlappingDays(int DaysFrom1, int DaysTo1, int DaysFrom2, int DaysTo2) {
    var maxFrom = DaysFrom1 > DaysFrom2 ? DaysFrom1 : DaysFrom2;
    var minTo = DaysTo1 < DaysTo2 ? DaysTo1 : DaysTo2;
    return (minTo > maxFrom) ? minTo - maxFrom : 0;
}

var dgs = data.Select(d => {
    var DaysFrom = (d.DateFrom - baseDate).Days;
    var DaysTo = (d.DateTo - baseDate).Days;
    return (d.Id, DaysFrom, DaysTo, Dist: DaysTo - DaysFrom);
})
              .GroupBy(d => d.Id)
              .Select(dg => (Id: dg.Key, Group: dg, Dist: dg.Sum(d => d.Dist)))
              .ToList();

var MaxOverlappingPair = (Id1: 0, Id2: 0, OverlapInDays: 0);

for (int j1 = 0; j1 < dgs.Count; ++j1) {
    var dg1 = dgs[j1];
    if (dg1.Dist > MaxOverlappingPair.OverlapInDays)
        for (int j2 = j1 + 1; j2 < dgs.Count; ++j2) {
            var dg2 = dgs[j2];
            if (dg2.Dist > MaxOverlappingPair.OverlapInDays) {
                var testOverlapInDays = 0;
                foreach (var d1 in dg1.Group)
                    foreach (var d2 in dg2.Group)
                        testOverlapInDays += OverlappingDays(d1.DaysFrom, d1.DaysTo, d2.DaysFrom, d2.DaysTo);

                if (testOverlapInDays > MaxOverlappingPair.OverlapInDays)
                    MaxOverlappingPair = (dg1.Id, dg2.Id, testOverlapInDays);
            }
        }
}

应用的优化:

1. 转换每个跨距 DateTime 从 arbitrary baseDate 通过执行一次日期转换来优化重叠天数计算。
2. 计算每个跨度的总天数,并跳过任何不能超过当前重叠的跨度对
3. 代替 SelectMany / Select 带嵌套 foreach 计算重叠天数。
4. 使用 ValueTuple s而不是匿名对象,匿名对象对此问题的处理速度(稍微)更快。
5. 将对生成LINQ替换为嵌套 for 直接生成每个可能对的循环
6. 将单个自/到参数而不是对象传递到 OverlappingDays 作用

注意:我尝试了一个更智能的重叠天数计算,但当每个ID的跨度数很小时,开销要比直接计算花费更长的时间。

解决方案已经很少

但是

如果要提高效率,则不必将每个对象/值与其他任何值或对象进行比较。您可以使用 Interval Search Tree 对于这个问题,可以在 RlogN 哪里 R 是间隔之间的交点数。

我建议你看这个 video 罗伯特·塞奇威克(RobertSedgwick)的著作,这本书也可以在线阅读。

这里的基本问题是如何确定一组唯一的时间段。给每个人自己一个独特的ID。

在编写最终答案时,请在输出中包含其他详细信息,以便用户能够了解最终答案是由哪些(原始)ID和原始时间段产生的。

记住-问题仍然与原始帖子中的相同( https://codereview.stackexchange.com/questions/186014/finding-the-longest-overlapping-period/186031?noredirect=1#comment354707_186031 )你仍然有相同的信息要处理。不要过于关注原始列表中提供的“ID”——您仍在迭代时间段列表。