Skip to content

2251. Number of Flowers in Full Bloom 👍

  • Time: $O(\texttt{sort} + |\texttt{persons}|\log n)$
  • Space: $O(n + |\texttt{persons}|)$
 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
class Solution {
 public:
  vector<int> fullBloomFlowers(vector<vector<int>>& flowers,
                               vector<int>& persons) {
    vector<int> ans;
    vector<int> starts;
    vector<int> ends;

    for (const vector<int>& flower : flowers) {
      starts.push_back(flower[0]);
      ends.push_back(flower[1]);
    }

    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    for (const int p : persons) {
      const int started =
          upper_bound(starts.begin(), starts.end(), p) - starts.begin();
      const int ended = lower_bound(ends.begin(), ends.end(), p) - ends.begin();
      ans.push_back(started - ended);
    }

    return ans;
  }
};

 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
class Solution {
  public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
    int[] ans = new int[persons.length];
    List<Integer> starts = new ArrayList<>();
    List<Integer> ends = new ArrayList<>();

    for (int[] flower : flowers) {
      starts.add(flower[0]);
      ends.add(flower[1]);
    }

    Collections.sort(starts);
    Collections.sort(ends);

    for (int i = 0; i < persons.length; ++i) {
      final int started = firstGreater(starts, persons[i]);
      final int ended = firstGreaterEqual(ends, persons[i]);
      ans[i] = started - ended;
    }

    return ans;
  }

  // Finds the first index l s.t A.get(l) > target.
  // Returns A.size() if can't find.
  private int firstGreater(List<Integer> A, int target) {
    int l = 0;
    int r = A.size();
    while (l < r) {
      final int m = (l + r) / 2;
      if (A.get(m) > target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }

  // Find the first index l s.t A.get(l) >= target
  // Returns A.size() if can't find
  private int firstGreaterEqual(List<Integer> A, int target) {
    int l = 0;
    int r = A.size();
    while (l < r) {
      final int m = (l + r) / 2;
      if (A.get(m) >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

1
2
3
4
5
6
7
class Solution:
  def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
    starts = sorted(s for s, _ in flowers)
    ends = sorted(e for _, e in flowers)
    return [bisect.bisect_right(starts, person) -
            bisect.bisect_left(ends, person)
            for person in persons]