Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
You are given a 0-indexed 2D integer array flowers
, where flowers[i] = [starti, endi]
means the ith
flower will be in full bloom from starti
to endi
(inclusive). You are also given a 0-indexed integer array persons
of size n
, where persons[i]
is the time that the ith
person will arrive to see the flowers.
Return an integer array answer
of size n
, where answer[i]
is the number of flowers that are in full bloom when the ith
person arrives.
Example 1:
Input: flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
Output: [1,2,2,2]
Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.
Example 2:
Input: flowers = [[1,10],[3,3]], persons = [3,3,2]
Output: [2,2,1]
Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.
Constraints:
1 <= flowers.length <= 5 * 104
flowers[i].length == 2
1 <= starti <= endi <= 109
1 <= persons.length <= 5 * 104
1 <= persons[i] <= 109
vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
vector<int> start, end;
for (auto& t : flowers)
start.push_back(t[0]), end.push_back(t[1]);
sort(start.begin(), start.end());
sort(end.begin(), end.end());
vector<int> res;
for (int t : persons) {
int started = upper_bound(start.begin(), start.end(), t) - start.begin();
int ended = lower_bound(end.begin(), end.end(), t) - end.begin();
res.push_back(started - ended);
}
return res;
}
def fullBloomFlowers(self, A: List[List[int]], persons: List[int]) -> List[int]:
start, end = sorted(a for a,b in A), sorted(b for a,b in A)
return [bisect_right(start, t) - bisect_left(end, t) for t in persons]
public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
/*3 events:
0 - Bloom
1 - Person
2 - Die
*/
//{time position, event type, if person -> index}
//first sort by time, then by event type
Queue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
//add the person events
for(int i = 0; i < persons.length; i++){
//for person also add what index they were - {time position, human, index}
pq.offer(new int[]{persons[i], 1, i});
}
//add the blossom events
for(int[] flower : flowers){
pq.offer(new int[]{flower[0], 0});
pq.offer(new int[]{flower[1], 2});
}
//traverse them all
int[] ret = new int[persons.length];
int numEvents = pq.size();
int blooms = 0;
for(int i = 0; i < numEvents; i++){
int[] cur = pq.poll();
//if bloom, increment blooms
if(cur[1] == 0){
blooms++;
//if die, decrement blooms
}else if(cur[1] == 2){
blooms--;
//if person, set their index to # blooms
}else{
int personIndex = cur[2];
ret[personIndex] = blooms;
}
}
return ret;
}
In our experience, we suggest you solve this Number of Flowers in Full Bloom LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Number of Flowers in Full Bloom LeetCode Solution
I hope this Number of Flowers in Full Bloom LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>