linq 重叠对象列表

jvidinwx  于 2022-12-06  发布在  其他
关注(0)|答案(4)|浏览(151)

我有以下
var list = new List<Schedule>();
Schedule对象具有以下属性:

  • 开始时间(日期时间)
  • 结束时间(日期时间)

是否有一行代码可以在遍历Schedule的所有成员时检查list中的时间约束是否重叠?
先谢谢你。
我试图在一个名为EnforceOverlapPolicy()的方法中使用上述逻辑,如果存在任何冲突,从技术上讲,该方法将抛出一个新的异常。

vhmi4jdf

vhmi4jdf1#

如果您只关心是否存在重叠,而不关心哪些计划重叠,那么您应该能够在O(n log n)。关键是按StartTimeEndTime对计划进行排序然后你可以枚举结果并将每个调度的StartTime与前一个调度的EndTime进行比较。如果StartTime早于EndTime,那么您就有了重叠的调度。但是,如果没有第三方的帮助,我不认为这可以在一个查询中完成。我自己就是Ix-Main的爱好者。下面的解决方案使用了Ix-Main中的Buffer函数:

bool hasOverlap =
    list
    .OrderBy(x => x.StartTime)
    .ThenBy(x => x.EndTime)
    .Buffer(2, 1)
    .Where(x => x.Count == 2)
    .Where(x => x[1].StartTime < x[0].EndTime)
    .Any();

如果您不想使用第三方库,则可以使用以下库执行相同的操作:

Schedule first = null;
bool hasOverlap = false;
using(var enumerator = list.OrderBy(x => x.StartTime).ThenBy(x => x.EndTime).GetEnumerator())
{
    enumerator.MoveNext();
    first = enumerator.Current;
    while(enumerator.MoveNext())
    {
        if(enumerator.Current.StartTime < first.EndTime)
        {
            hasOverlap = true;
            break;
        }
    }
}
qlvxas9a

qlvxas9a2#

假设性能不是问题(否则考虑an algorithm for overlaps):

var pairs = from f in list 
            from s in list
            where (f.EndTime < s.StartTime) && (f.StartTime < s.EndTime) && (f != s)
            select new {First = f, Second = s };

基本上,我们在检查所有可能的配对是否有重叠。
或者,如果不使用查询语法:

var overlaps = list.SelectMany(l => list, (f, s) => new {f,s})
    .Where(x => (x.f.EndTime < x.s.StartTime) && 
               (x.f.StartTime < x.s.EndTime) && (x.f != x.s));
xpszyzbs

xpszyzbs3#

一种不同的方法,我不确定整个事情的性能,但想法是在BitArray中展平由您的时间表定义的范围,如果特定的分钟已经被前一个时间表使用,则发出信号。
从技术上讲,它也不是“一行”的答案,尽管从调用代码的Angular 来看,它只是一行
因此假设已经定义了类ScheduleList

public class ScheduleList : List<Schedule>
{
    private BitArray ba = new BitArray(1440);

    // Define own Add method to Add a Schedule to the list
    // Or override the predefined one....
    public Schedule Add(int sh, int sm, int eh, int em)
    {
        Schedule s = new Schedule();
        s.StartTime = new DateTime(1, 1, 1, sh, sm, 0);
        s.EndTime = new DateTime(1, 1, 1, eh, em, 0);

        // Of course, having full control on the Add phase, you
        // could easily enforce your policy at this point. 
        // You could not accept a new schedule if the time slot is busy
        // but we could ignore it at this point

        this.Add(s);
        return s;
    }

    public bool IsTimeSlotBusy(Schedule s)
    {
        int sidx = Convert.ToInt32(TimeSpan.FromMinutes((s.StartTime.Hour * 60) + s.StartTime.Minute).TotalMinutes);
        int eidx = Convert.ToInt32(TimeSpan.FromMinutes((s.EndTime.Hour * 60) + s.EndTime.Minute).TotalMinutes);
        for (int x = sidx; x <= eidx; x++)
        {
            if (ba.Get(x)) return true;
            ba.Set(x, true);
        }
        return false;
    }
}

现在你可以这样写

ScheduleList schedules = new ScheduleList();
schedules.Add(12, 0, 12, 30);
schedules.Add(15, 10, 15, 30);
schedules.Add(12, 0, 23, 59);
schedules.Add(14, 0, 23, 59);

// The fake 'one liner'
bool overlap = schedules.Any(s => schedules.IsTimeSlotBusy(s));
Console.WriteLine(overlap);

等待这里的数学家告诉我为什么这是最糟糕的。(不是讽刺,我真的希望知道这是不是从数学的Angular 来看是不好的)

z4iuyo4d

z4iuyo4d4#

public static bool DoesNotOverlap(List<Schedule> timeSlots)
{
    DateTime endPrior = DateTime.MinValue;

    foreach (Schedule timeSlot in timeSlots.OrderBy(x => x.StartTime))
    {
        if (timeSlot.StartTime > timeSlot.EndTime || timeSlot.StartTime < endPrior)
            return false;
        endPrior = timeSlot.End;
    }

    return true;
}

对于任何需要此功能的人,它不是问题所要求的一行程序,而是解决检查重叠DateTime元素与Start和End日期问题的简单方法
1.使用OrderBy Linq运算符对列表进行排序。
1.不允许开始DateTime大于结束DateTime
1.跟踪以前每次会议的结束时间,查看它是否与计划的DateTime的下一次开始时间重叠。

相关问题