【解惑】時間規劃,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)是操作系統能夠進行運算調度的最小單位。它被包含在進程之中,是進程中的實際 運作單位。一條線程指的是進程中一個單一順序的控制流,一個進程中可以併發多個線程,每條線 程並行執行不同的任務。 ...
  • 背景介紹 1,最近有一個大數據量插入的操作入庫的業務場景,需要先做一些其他修改操作,然後在執行插入操作,由於插入數據可能會很多,用到多線程去拆分數據並行處理來提高響應時間,如果有一個線程執行失敗,則全部回滾。 2,在spring中可以使用@Transactional註解去控制事務,使出現異常時會進行 ...
  • 在`Windows`操作系統中,每個進程的虛擬地址空間都被劃分為若幹記憶體塊,每個記憶體塊都具有一些屬性,如記憶體大小、保護模式、類型等。這些屬性可以通過`VirtualQueryEx`函數查詢得到。該函數可用於查詢進程虛擬地址空間中的記憶體信息的函數。它的作用類似於`Windows`操作系統中的`Task... ...
  • 大家好,我是沙漠盡頭的狼。 本方首發於Dotnet9,介紹使用dnSpy調試第三方.NET庫源碼,行文目錄: 安裝dnSpy 編寫示常式序 調試示常式序 調試.NET庫原生方法 總結 1. 安裝dnSpy dnSpy是一款功能強大的.NET程式反編譯工具,可以對.NET程式進行反編譯,代替庫文檔的功 ...
  • 框架目標 什麼是框架,框架能做到什麼? 把一個方向的技術研發做封裝,具備通用性,讓使用框架的開發者用起來很輕鬆。 屬性: 通用性 健壯性 穩定性 擴展性 高性能 組件化 跨平臺 從零開始-搭建框架 建立項目 主鍵查詢功能開發 綁定實體 一步一步的給大家推導: 一邊寫一邊測試 從零開始--搭建框架 1 ...
  • 剛開始寫文章,封裝Base基類的時候,添加了trycatch異常塊,不過當時沒有去記錄日誌,直接return了。有小伙伴勸我不要吃了Exception 其實沒有啦,項目剛開始,我覺得先做好整體結構比較好。像是蓋樓一樣。先把樓體建造出來,然後再一步一步的美化完善。 基礎的倉儲模式已經ok,Autofa ...
  • 一:背景 1. 講故事 最近也挺奇怪,看到了兩起 CPU 爆高的案例,且誘因也是一致的,覺得有一些代表性,合併分享出來幫助大家來避坑吧,閑話不多說,直接上 windbg 分析。 二:WinDbg 分析 1. CPU 真的爆高嗎 這裡要提醒一下,別人說爆高不一定真的就是爆高,我們一定要拿數據說話,可以 ...
  • 簡介 Flurl是一個用於構建基於HTTP請求的C#代碼的庫。它的主要目的是簡化和優雅地處理網路請求(只用很少的代碼完成請求)。Flurl提供了一種簡單的方法來構建GET、POST、PUT等類型的請求,以及處理響應和異常。它還提供了一些高級功能,如鏈式調用、緩存請求結果、自動重定向等。本文將介紹Fl ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...