一、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 }