Number of Flowers in Full Bloom

hard intervals binary search sweep

Problem

Each flower i blooms over an inclusive time window [start, end], and each visitor arrives at some time t. For every visitor, report how many flowers are in full bloom at the exact moment they arrive. Both lists can hold up to 5·10⁴ entries and times go up to 10⁹, so checking every flower per visitor is too slow.

Inputflowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]

Output[1,2,2,2]

At t=2 only [1,6] is open; at t=3 [1,6] and [3,7]; at t=7 [3,7] and [4,13]; at t=11 [9,12] and [4,13].

flowers (start:end, comma-separated)

people (arrival times, comma-separated)

from bisect import bisect_left, bisect_right

def full_bloom_flowers(flowers, people):
    starts = sorted(f[0] for f in flowers)
    ends = sorted(f[1] for f in flowers)
    ans = []
    for t in people:
        started = bisect_right(starts, t)
        ended = bisect_left(ends, t)
        ans.append(started - ended)
    return ans

function fullBloomFlowers(flowers, people) {
  const starts = flowers.map(f => f[0]).sort((a, b) => a - b);
  const ends = flowers.map(f => f[1]).sort((a, b) => a - b);
  function countLE(arr, x) {        // how many values <= x
    let lo = 0, hi = arr.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid] <= x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
  const ans = [];
  for (const t of people) {
    const started = countLE(starts, t);
    const ended = countLE(ends, t - 1);   // end < t
    ans.push(started - ended);
  }
  return ans;
}

int[] fullBloomFlowers(int[][] flowers, int[] people) {
    int n = flowers.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = flowers[i][0]; ends[i] = flowers[i][1]; }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int[] ans = new int[people.length];
    for (int i = 0; i < people.length; i++) {
        int started = countLE(starts, people[i]);
        int ended = countLE(ends, people[i] - 1);   // end < t
        ans[i] = started - ended;
    }
    return ans;
}

int countLE(int[] arr, int x) {   // how many values <= x
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (arr[mid] <= x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
    int n = flowers.size();
    vector<int> starts(n), ends(n);
    for (int i = 0; i < n; i++) {
        starts[i] = flowers[i][0];
        ends[i] = flowers[i][1];
    }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    vector<int> ans;
    for (int t : people) {
        int started = upper_bound(starts.begin(), starts.end(), t) - starts.begin();
        int ended = lower_bound(ends.begin(), ends.end(), t) - ends.begin();
        ans.push_back(started - ended);
    }
    return ans;
}

Explanation

The key insight is that we never need to know which flowers are blooming at time t, only how many. A flower is in bloom at t exactly when it has started (start ≤ t) and has not yet finished (end ≥ t). So the count is simply (flowers that started by t) − (flowers that finished before t). That subtraction lets us decouple the starts from the ends entirely.

We pull all start times into one array and all end times into another and sort each independently. It does not matter that a sorted start no longer sits next to its own end — counting is all we do. Now each visitor query becomes two binary searches: bisect_right(starts, t) counts starts ≤ t, and bisect_left(ends, t) counts ends strictly less than t. The strict inequality on ends matters because the bloom window is inclusive: a flower whose end equals t is still open when the visitor arrives.

Walk through the default example: starts = [1,3,4,9], ends = [6,7,12,13]. The visitor at t=2 finds 1 start ≤ 2 and 0 ends < 2, so 1 flower is open. At t=3: 2 started, 0 ended → 2. At t=7: 3 started, but the flower ending at 6 has wilted, so 3 − 1 = 2. At t=11: all 4 started, ends 6 and 7 have passed, 4 − 2 = 2. The answer is [1,2,2,2].

This is really a sweep idea in disguise: imagine walking the timeline left to right, adding 1 at every start and subtracting 1 just after every end — the running sum at any moment is the bloom count. Sorting starts and ends separately and binary searching just evaluates that running sum at any t directly, without replaying the whole sweep per query.

Sorting the two arrays costs O(n log n), and each of the m visitors does two O(log n) binary searches, for O((n + m) log n) total — comfortably fast for 5·10⁴ of each. The extra space is the two sorted arrays, O(n), beyond the output itself.

Time: O((n + m) log n) Space: O(n)