-
Notifications
You must be signed in to change notification settings - Fork 0
/
Q2251_Number_of_Flowers_in_FullBloom.cs
54 lines (45 loc) · 1.5 KB
/
Q2251_Number_of_Flowers_in_FullBloom.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Solution {
public int[] FullBloomFlowers(int[][] flowers, int[] persons)
{
var changesQueue = new PriorityQueue<int, int>();
foreach (var bloomPeriod in flowers)
{
changesQueue.Enqueue(1, bloomPeriod[0]);
changesQueue.Enqueue(-1, bloomPeriod[1] + 1);
}
var changesHistory = new List<(int numberOfFlowersInFullBloom, int time)>();
changesHistory.Add((0, 0));
var inFullBloom = 0;
while (changesQueue.TryDequeue(out var change, out var time))
{
inFullBloom += change;
if (changesHistory.Count > 0 && changesHistory[^1].time == time)
{
changesHistory[^1] = (inFullBloom, time);
}
else
{
changesHistory.Add((inFullBloom, time));
}
}
return persons.Select(GetNumberOfFlowersInFullBloomByTime).ToArray();
int GetNumberOfFlowersInFullBloomByTime(int time)
{
var l = 0;
var r = changesHistory.Count - 1;
while (l < r)
{
var mid = (l + r + 1) / 2;
if (time >= changesHistory[mid].time)
{
l = mid;
}
else
{
r = mid - 1;
}
}
return changesHistory[l].numberOfFlowersInFullBloom;
}
}
}