Hard

Number of Flowers in Full Bloom

LAB

Given flower intervals and query times, return how many flowers are blooming at each query time.

EXAMPLES

Example 1

Input
{
  "flowers": [
    [
      1,
      6
    ],
    [
      3,
      7
    ],
    [
      9,
      12
    ],
    [
      4,
      13
    ]
  ],
  "people": [
    2,
    3,
    7,
    11
  ]
}

Output
[
  1,
  2,
  2,
  2
]

FUNCTION SHAPE

flowers: intMatrixpeople: intArray→intArray

SOLUTION NOTE

This is pretty simple. Just do the line sweep and simulate. We accumulate all the flowers up until this person p in lines, and that is the number of active flowers that person can see.

You can also do this with a min heap, in a very similar logic. Just maintain a heap of active flowers end times. At the beginning we add all flowers who start before this person time. And we pop all the flowers that ended before this persons time. The remaining flowers in the heap are all the ones that started before this person and ended after this person.

Reveal reference solution +

pythonREFERENCE

# Line sweep solution
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
    people = [(p, i) for i, p in enumerate(people)]
    people.sort()
    lines = defaultdict(int)

    for s, e in flowers:
        lines[s] += 1
        lines[e+1] -= 1

    line_keys = sorted(lines)

    idx = 0
    cum_sum = 0
    res = [-1] * len(people)

    for p, i in people:
        while idx < len(line_keys) and line_keys[idx] <= p:
            cum_sum += lines[line_keys[idx]]
            idx += 1
        res[i] = cum_sum

    return res

# Heap solution
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
    flowers.sort()
    sorted_people = sorted(people)
    dic = {}
    active_flowers = []

    i = 0
    for person in sorted_people:
        while i < len(flowers) and flowers[i][0] <= person:
            heapq.heappush(active_flowers, flowers[i][1])
            i += 1

        while active_flowers and active_flowers[0] < person:
            heapq.heappop(active_flowers)

        dic[person] = len(active_flowers)

    return [dic[x] for x in people]

TimeO((n + m) log (n + m))

SpaceO(n + m)

Open on LeetCode ↗