【解惑】时间规划,Linq的Aggregate函数在计算会议重叠时间中的应用

  • 【解惑】时间规划,Linq的Aggregate函数在计算会议重叠时间中的应用已关闭评论
  • 70 次浏览
  • A+
所属分类:.NET技术
摘要

在繁忙的周五,小悦坐在会议室里,面前摆满了各种文件和会议安排表。她今天的工作任务是为公司安排下周的50个小会议,这让她感到有些头疼。但是,她深吸了一口气,决定耐心地一个一个去处理。

在繁忙的周五,小悦坐在会议室里,面前摆满了各种文件和会议安排表。她今天的工作任务是为公司安排下周的50个小会议,这让她感到有些头疼。但是,她深吸了一口气,决定耐心地一个一个去处理。

首先,小悦仔细地收集了每个会议的相关信息,包括会议的主题、目的、预计参加人数、所需设备和预计的开始和结束时间等。她需要这些信息来计算所有会议的总时间长度,以便能够合理安排时间表。

小悦开始了紧张的计算。汗水从她的额头滑落,但她顾不得擦,她紧盯着电脑屏幕,手在键盘上快速敲击着。会议室里的空调仿佛失效了一般,让她感觉热浪滚滚,但她心无旁骛,专注于手头的工作。

会议1的时间是13-16点,会议2的时间是13-17点,总长度为4小时。计算这个总长度4的意义在于……小悦的思绪在飞舞,她在考虑如何避免时间冲突,如何规划时间表,如何评估时间利用率。

突然,她发现会议1和会议2存在时间上的重叠,这可能导致参与者无法同时参加这两个会议,或者无法充分参与其中一个会议。她赶紧与相关部门取得联系,将这个问题进行了及时调整。

解决了若干个冲突后,终于完成了所有的计算和安排,将邮件发送出去之后,小悦松了一口气。她走到窗边,擦了擦额头上的汗珠,看着窗外已经开始昏暗的天空。尽管此刻她已经感到身心疲惫,但是看到自己的工作成果,她心中充满了满足和自豪。

这时,手机突然响起,是领导打来的电话。“小悦,这次会议安排得非常出色,你做得很好!”领导的赞赏让小悦的疲惫感瞬间消失得无影无踪。她知道,这是对她努力工作的最好肯定。

这个周五,小悦不仅完成了艰巨的任务,还学到了很多东西。她明白,只有通过精确的计算和科学的规划,才能最大限度地提高会议效率,避免资源的浪费。同时,她也意识到,要时刻关注细节,只有这样才能发现问题,解决问题。

虽然今天的工作很累,但是小悦感到非常有收获。她坚信,只要用心去做,无论任务多么艰巨,都能做到最好。在未来的道路上,她将继续倾尽全力,充分展现自己的价值。

小悦遇到的其中一个问题是计算所有会议时间的总长度,编写一个名为SumIntervals的函数,该函数接受一个区间数组,并返回所有区间长度的总和。重叠间隔只能计算一次。

间隔区间由一对数组形式的整数表示。间隔的第一个值将始终小于第二个值。区间示例:[1,5]是从1到5的区间。这个间隔的长度是4。

示例:

[

[1,4],

[7,10],

[3,5]

]

由于[1,4]和[3,5]部分重叠,我们可以将这两个区间视为[1,5],其长度为4,而[7,10]的长度是3。所以这些间隔的总长度之和是7。


算法实现1:

 1 public static int SumIntervals((int, int)[] intervals)  2 {  3     if (intervals == null || intervals.Length == 0)  4         return 0;  5   6     Array.Sort(intervals, (a, b) => a.Item1.CompareTo(b.Item1));  7   8     int result = 0; // 初始化结果为0  9     int start = intervals[0].Item1; // 初始化起始时间为第一个区间的起始时间 10     int end = intervals[0].Item2; // 初始化结束时间为第一个区间的结束时间 11  12     for (int i = 1; i < intervals.Length; i++) // 遍历剩余的区间 13     { 14         if (intervals[i].Item1 <= end) // 如果当前区间的起始时间小于等于上一个区间的结束时间 15         { 16             end = Math.Max(end, intervals[i].Item2); // 更新结束时间为当前区间和上一个区间的结束时间中的较大值 17         } 18         else // 如果当前区间的起始时间大于上一个区间的结束时间 19         { 20             result += end - start; // 将上一个区间的长度累加到结果中 21             start = intervals[i].Item1; // 更新起始时间为当前区间的起始时间 22             end = intervals[i].Item2; // 更新结束时间为当前区间的结束时间 23         } 24     } 25  26     result += end - start; // 将最后一个区间的长度累加到结果中 27  28     return result; // 返回总长度 29 }

这段代码实现了一个函数 `SumIntervals`,该函数接受一个由元组 `(int, int)` 组成的数组 `intervals` 作为参数,并计算这些区间的总长度。

代码的逻辑如下:

1. 首先,对传入的区间数组进行排序,按照区间的起始时间从小到大进行排序。

2. 初始化结果 `result` 为0,起始时间 `start` 为第一个区间的起始时间,结束时间 `end` 为第一个区间的结束时间。

3. 从第二个区间开始遍历剩余的区间。如果当前区间的起始时间小于等于上一个区间的结束时间,说明这两个区间有重叠部分,更新结束时间为当前区间和上一个区间的结束时间中的较大值。

4. 如果当前区间的起始时间大于上一个区间的结束时间,说明这两个区间没有重叠部分,将上一个区间的长度累加到结果中,更新起始时间为当前区间的起始时间,结束时间为当前区间的结束时间。

5. 遍历结束后,将最后一个区间的长度累加到结果中。

6. 返回结果,即总长度。


算法实现2:

1 public static int SumIntervals((int min, int max)[] intervals) 2 { 3     var prevMax = int.MinValue; 4      5     return intervals 6         .OrderBy(x => x.min) 7         .ThenBy(x => x.max) 8         .Aggregate(0, (acc, x) => acc += prevMax < x.max ? - Math.Max(x.min, prevMax) + (prevMax = x.max) : 0); 9 }

算法2和算法1的实现效果是完全一样的,在算法2中,`Aggregate`函数用于在一系列元素上执行累积操作。它被用来计算区间的总和。

以下是如何在代码中使用`Aggregate`的步骤说明:

1. 首先,使用`OrderBy`对`intervals`数组进行排序,以确保按照区间的最小值升序处理。如果最小值相同,则使用`ThenBy`按照最大值升序排序。

2. 然后,在排序后的区间上调用`Aggregate`函数。它接受两个参数:
- 累积的初始值,在这个例子中是`0`。
- 一个lambda表达式`(acc, x) => acc += prevMax < x.max ? - Math.Max(x.min, prevMax) + (prevMax = x.max) : 0`,定义了累积逻辑。

3. lambda表达式`(acc, x) => acc += prevMax < x.max ? - Math.Max(x.min, prevMax) + (prevMax = x.max) : 0`用于计算区间的总和。它有两个参数:
- `acc`:当前的累积值。
- `x`:当前正在处理的区间。

4. 在lambda表达式内部,逻辑如下:
- 如果`prevMax`(前一个区间的最大值)小于当前区间的最大值(`prevMax < x.max`),则当前区间与前一个区间重叠或延伸。
- 在这种情况下,累积值`acc`通过从`acc`中减去当前区间的最小值和`prevMax`的最大值,并加上当前区间的最大值来更新(`- Math.Max(x.min, prevMax) + (prevMax = x.max)`)。
- 如果`prevMax`不小于当前区间的最大值,则当前区间与前一个区间不重叠或延伸,累积值保持不变(`: 0`)。

5. `Aggregate`函数的最终结果作为区间的总和返回。

以下是使用给定代码的`Aggregate`函数的用法示例:

在这个示例中,测试数据如下:
```
(1, 4)
(2, 5)
(6, 8)
(7, 9)
(10, 12)
```

Aggregate详细计算步骤如下:

1. 初始化累积值 `acc` 为 `0`。
2. 对区间数组进行升序排序,得到 `[(1, 4), (2, 5), (6, 8), (7, 9), (10, 12)]`。
3. 处理第一个区间 `(1, 4)`:
- 由于 `prevMax` 小于 `4`,累积值更新为 `0 - Math.Max(1, prevMax) + (prevMax = 4) = 0 - Math.Max(1, int.MinValue) + (prevMax = 4) = 0 - 1 + 4 = 3`。
4. 处理第二个区间 `(2, 5)`:
- 由于 `prevMax` 小于 `5`,累积值更新为 `3 - Math.Max(2, prevMax) + (prevMax = 5) = 3 - Math.Max(2, 4) + (prevMax = 5) = 3 - 4 + 5 = 4`。
5. 处理第三个区间 `(6, 8)`:
- 由于 `prevMax` 小于 `8`,累积值更新为 `4 - Math.Max(6, prevMax) + (prevMax = 8) = 4 - Math.Max(6, 5) + (prevMax = 8) = 4 - 6 + 8 = 6`。
6. 处理第四个区间 `(7, 9)`:
- 由于 `prevMax` 小于 `9`,累积值更新为 `6 - Math.Max(7, prevMax) + (prevMax = 9) = 6 - Math.Max(7, 8) + (prevMax = 9) = 6 - 8 + 9 = 7`。
7. 处理第五个区间 `(10, 12)`:
- 由于 `prevMax` 小于 `12`,累积值更新为 `7 - Math.Max(10, prevMax) + (prevMax = 12) = 7 - Math.Max(10, 9) + (prevMax = 12) = 7 - 10 + 12 = 9`。
8. 累积操作结束,返回最终的累积值 `9`。

以上两段代码的作用是一样的,计算一组区间的总长度,可以用于避免时间冲突、规划时间表等场景中。


测试用例:

  1 using NUnit.Framework;   2 using System;   3 using System.Collections.Generic;   4 using System.Linq;   5    6 using In = System.ValueTuple<int, int>;   7    8 public class IntervalTest   9 {  10     private In[] Shuffle(In[] a)  11     {  12         List<In> list = new List<In>(a);  13         Shuffle(list);  14         return list.ToArray();  15     }  16   17     private static void Shuffle<T>(List<T> deck)  18     {  19         var rnd = new Random();  20         for (int n = deck.Count - 1; n > 0; --n)  21         {  22             int k = rnd.Next(n + 1);  23             T temp = deck[n];  24             deck[n] = deck[k];  25             deck[k] = temp;  26         }  27     }  28   29     private int ShuffleAndSumIntervals(In[] arg)  30     {  31         return Intervals.SumIntervals(Shuffle(arg));  32     }  33   34     [Test]  35     public void ShouldHandleEmptyIntervals()  36     {  37         Assert.AreEqual(0, Intervals.SumIntervals(new In[] { }));  38         Assert.AreEqual(0, ShuffleAndSumIntervals(new In[] { (4, 4), (6, 6), (8, 8) }));  39     }  40   41     [Test]  42     public void ShouldAddDisjoinedIntervals()  43     {  44         Assert.AreEqual(9, ShuffleAndSumIntervals(new In[] { (1, 2), (6, 10), (11, 15) }));  45         Assert.AreEqual(11, ShuffleAndSumIntervals(new In[] { (4, 8), (9, 10), (15, 21) }));  46         Assert.AreEqual(7, ShuffleAndSumIntervals(new In[] { (-1, 4), (-5, -3) }));  47         Assert.AreEqual(78, ShuffleAndSumIntervals(new In[] { (-245, -218), (-194, -179), (-155, -119) }));  48     }  49   50     [Test]  51     public void ShouldAddAdjacentIntervals()  52     {  53         Assert.AreEqual(54, ShuffleAndSumIntervals(new In[] { (1, 2), (2, 6), (6, 55) }));  54         Assert.AreEqual(23, ShuffleAndSumIntervals(new In[] { (-2, -1), (-1, 0), (0, 21) }));  55     }  56   57     [Test]  58     public void ShouldAddOverlappingIntervals()  59     {  60         Assert.AreEqual(7, ShuffleAndSumIntervals(new In[] { (1, 4), (7, 10), (3, 5) }));  61         Assert.AreEqual(6, ShuffleAndSumIntervals(new In[] { (5, 8), (3, 6), (1, 2) }));  62         Assert.AreEqual(19, ShuffleAndSumIntervals(new In[] { (1, 5), (10, 20), (1, 6), (16, 19), (5, 11) }));  63     }  64   65     [Test]  66     public void ShouldHandleMixedIntervals()  67     {  68         Assert.AreEqual(13, ShuffleAndSumIntervals(new In[] { (2, 5), (-1, 2), (-40, -35), (6, 8) }));  69         Assert.AreEqual(1234, ShuffleAndSumIntervals(new In[] { (-7, 8), (-2, 10), (5, 15), (2000, 3150), (-5400, -5338) }));  70         Assert.AreEqual(158, ShuffleAndSumIntervals(new In[] { (-101, 24), (-35, 27), (27, 53), (-105, 20), (-36, 26) }));  71     }  72     73     [Test]  74     public void ShouldHandleLargeIntervals()  75     {  76         Assert.AreEqual(2_000_000_000, Intervals.SumIntervals(new In[] { (-1_000_000_000, 1_000_000_000) }));  77         Assert.AreEqual(100_000_030, Intervals.SumIntervals(new In[] { (0, 20), (-100_000_000, 10), (30, 40) }));  78     }  79   80     [Test]  81     public void ShouldHandleSmallRandomIntervals()  82     {  83       RandomTests(1, 20, -500, 500, 1, 20);  84     }  85   86     [Test]  87     public void ShouldHandleLargeRandomIntervals()  88     {  89       RandomTests(20, 200, -1_000_000_000, 1_000_000_000, 1_000_000, 10_000_000);  90     }  91     92     private void RandomTests(int minN, int maxN, int minX, int maxX, int minW, int maxW)  93     {  94         for (int i = 0; i < 100; i++)  95         {  96             var intervals = GenerateRandomSeq(minN, maxN, minX, maxX, minW, maxW);  97             int expected = Expect(intervals);  98             int actual = Intervals.SumIntervals(intervals);  99             var msg = $"testing: {StringifyInterval(intervals)}"; 100             Assert.AreEqual(expected, actual, msg); 101         } 102     } 103  104     private In[] GenerateRandomSeq(int minN, int maxN, int minX, int maxX, int minW, int maxW) 105     { 106         var rnd = new Random(); 107         int total = rnd.Next(minN, maxN + 1); 108         var intervals = new In[total]; 109         for (int i = 0; i < total; i++) 110         { 111           int w = rnd.Next(minW, maxW + 1); 112           int x = rnd.Next(minX, maxX - w + 1); 113           intervals[i] = (x, x + w); 114         } 115         return intervals; 116     } 117  118     private string StringifyInterval(In[] i) => string.Join(", ", i.Select(x => $"[{string.Join(", ", x)}]")); 119  120     private int Expect((int lo, int hi)[] intervals) 121     { 122         if (intervals == null) return 0; 123         var sortedIntervals = intervals 124                 .Where(i => i.lo < i.hi) 125                 .OrderBy(i => i) 126                 .ToArray(); 127         if (sortedIntervals.Length == 0) return 0; 128         var lastHi = sortedIntervals[0].lo; 129         var sum = 0; 130         foreach (var (lo, hi) in sortedIntervals) 131         { 132             if (hi <= lastHi) 133                 continue; 134             sum += hi - (lo >= lastHi ? lo : lastHi); 135             lastHi = hi; 136         } 137         return sum; 138     } 139 }