Number of Flowers in Full Bloom

HardArrayHash TableBinary SearchSortingPrefix SumOrdered Set

Solution

export function fullBloomFlowers(flowers: number[][], people: number[]): number[] {
  const blooms = new Map();
  for (const [start, end] of flowers) {
    blooms.set(start, (blooms.get(start) ?? 0) + 1);
    blooms.set(end + 1, (blooms.get(end + 1) ?? 0) - 1);
  }
 
  const answer = new Array(people.length).fill(0);
  const times = [...blooms.keys()].sort((a, b) => a - b);
  const peopleWithIndex = people
    .map((time, peopleIndex) => ({ time, peopleIndex }))
    .sort((a, b) => a.time - b.time);
 
  let timeIndex = 0;
  let totalBlooms = 0;
  for (const { time, peopleIndex } of peopleWithIndex) {
    while (timeIndex < times.length && times[timeIndex] <= time) {
      totalBlooms += blooms.get(times[timeIndex]) ?? 0;
      timeIndex += 1;
    }
    answer[peopleIndex] = totalBlooms;
  }
  return answer;
}