【解惑】時間規劃，Linq的Aggregate函數在計算會議重疊時間中的應用

来源:https://www.cnblogs.com/lan80/archive/2023/09/22/17720891.html
-Advertisement-
Play Games

一、openKylin簡介 openKylin（開放麒麟） 社區是在開源、自願、平等和協作的基礎上，由基礎軟硬體企業、非營利性組織、社團組織、高等院校、科研機構和個人開發者共同創立的一個開源社區，致力於通過開源、開放的社區合作，構建桌面操作系統開源社區，推動Linux開源技術及其軟硬體生態繁榮發展。 ...


在繁忙的周五，小悅坐在會議室里，面前擺滿了各種文件和會議安排表。她今天的工作任務是為公司安排下周的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 }

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 深入淺出線程池
    線程(thread)是操作系統能夠進行運算調度的最小單位。它被包含在進程之中，是進程中的實際 運作單位。一條線程指的是進程中一個單一順序的控制流，一個進程中可以併發多個線程，每條線 程並行執行不同的任務。 ...
  • 支付寶一面：多線程事務怎麼回滾？說用 @Transactional 可以回去等通知了！
    背景介紹 1，最近有一個大數據量插入的操作入庫的業務場景，需要先做一些其他修改操作，然後在執行插入操作，由於插入數據可能會很多，用到多線程去拆分數據並行處理來提高響應時間，如果有一個線程執行失敗，則全部回滾。 2，在spring中可以使用@Transactional註解去控制事務，使出現異常時會進行 ...
  • 7.1 實現進程記憶體塊枚舉
    在`Windows`操作系統中，每個進程的虛擬地址空間都被劃分為若幹記憶體塊，每個記憶體塊都具有一些屬性，如記憶體大小、保護模式、類型等。這些屬性可以通過`VirtualQueryEx`函數查詢得到。該函數可用於查詢進程虛擬地址空間中的記憶體信息的函數。它的作用類似於`Windows`操作系統中的`Task... ...
  • 如何在沒有第三方.NET庫源碼的情況，調試第三庫代碼？
    大家好，我是沙漠盡頭的狼。 本方首發於Dotnet9，介紹使用dnSpy調試第三方.NET庫源碼，行文目錄： 安裝dnSpy 編寫示常式序 調試示常式序 調試.NET庫原生方法 總結 1. 安裝dnSpy dnSpy是一款功能強大的.NET程式反編譯工具，可以對.NET程式進行反編譯，代替庫文檔的功 ...
  • 一個簡易的ORM框架的實現(二)
    框架目標 什麼是框架，框架能做到什麼？ 把一個方向的技術研發做封裝，具備通用性，讓使用框架的開發者用起來很輕鬆。 屬性： 通用性 健壯性 穩定性 擴展性 高性能 組件化 跨平臺 從零開始-搭建框架 建立項目 主鍵查詢功能開發 綁定實體 一步一步的給大家推導： 一邊寫一邊測試 從零開始--搭建框架 1 ...
  • 5.使用日誌+自定義全局異常過濾器
    剛開始寫文章，封裝Base基類的時候，添加了trycatch異常塊，不過當時沒有去記錄日誌，直接return了。有小伙伴勸我不要吃了Exception 其實沒有啦，項目剛開始，我覺得先做好整體結構比較好。像是蓋樓一樣。先把樓體建造出來，然後再一步一步的美化完善。 基礎的倉儲模式已經ok，Autofa ...
  • 記一次 .NET 某儀器測量系統 CPU爆高分析
    一：背景 1. 講故事 最近也挺奇怪，看到了兩起 CPU 爆高的案例，且誘因也是一致的，覺得有一些代表性，合併分享出來幫助大家來避坑吧，閑話不多說，直接上 windbg 分析。 二：WinDbg 分析 1. CPU 真的爆高嗎 這裡要提醒一下，別人說爆高不一定真的就是爆高，我們一定要拿數據說話，可以 ...
  • .NET超簡單輕量級的HTTP請求組件Flurl
    簡介 Flurl是一個用於構建基於HTTP請求的C#代碼的庫。它的主要目的是簡化和優雅地處理網路請求（只用很少的代碼完成請求）。Flurl提供了一種簡單的方法來構建GET、POST、PUT等類型的請求，以及處理響應和異常。它還提供了一些高級功能，如鏈式調用、緩存請求結果、自動重定向等。本文將介紹Fl ...
一周排行
    -Advertisement-
    Play Games
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類