Number of Flowers in Full Bloom

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& queries) {
        vector<int> starts, ends;
        starts.reserve(flowers.size()); ends.reserve(flowers.size());
        for (auto& f : flowers) { starts.push_back(f[0]); ends.push_back(f[1]); }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        vector<int> ans;
        ans.reserve(queries.size());
        for (int q : queries) {
            int started = upper_bound(starts.begin(), starts.end(), q) - starts.begin();
            int ended = lower_bound(ends.begin(), ends.end(), q) - ends.begin();
            ans.push_back(started - ended);
        }
        return ans;
    }
};

import "sort"

func fullBloomFlowers(flowers [][]int, queries []int) []int {
    starts := make([]int, 0, len(flowers))
    ends := make([]int, 0, len(flowers))
    for _, f := range flowers {
        starts = append(starts, f[0])
        ends = append(ends, f[1])
    }
    sort.Ints(starts)
    sort.Ints(ends)
    ans := make([]int, 0, len(queries))
    for _, q := range queries {
        started := sort.SearchInts(starts, q+1) // upper_bound
        ended := sort.SearchInts(ends, q)       // lower_bound
        ans = append(ans, started-ended)
    }
    return ans
}

import bisect

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], queries: List[int]) -> List[int]:
        starts = sorted(f[0] for f in flowers)
        ends = sorted(f[1] for f in flowers)
        ans = []
        for q in queries:
            started = bisect.bisect_right(starts, q)
            ended = bisect.bisect_left(ends, q)
            ans.append(started - ended)
        return ans

function fullBloomFlowers(flowers, queries) {
    const starts = flowers.map(f => f[0]).sort((a, b) => a - b);
    const ends = flowers.map(f => f[1]).sort((a, b) => a - b);
    // upper_bound: first index with arr[i] > target
    const upperBound = (arr, t) => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (arr[m] <= t) lo = m + 1;
            else hi = m;
        }
        return lo;
    };
    // lower_bound: first index with arr[i] >= target
    const lowerBound = (arr, t) => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (arr[m] < t) lo = m + 1;
            else hi = m;
        }
        return lo;
    };
    const ans = [];
    for (const q of queries) {
        const started = upperBound(starts, q);
        const ended = lowerBound(ends, q);
        ans.push(started - ended);
    }
    return ans;
}

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] queries) {
        int n = flowers.length;
        int[] starts = new int[n];
        int[] 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[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int q = queries[i];
            int started = upperBound(starts, q);
            int ended = lowerBound(ends, q);
            ans[i] = started - ended;
        }
        return ans;
    }

    // first index with arr[i] > t
    private int upperBound(int[] arr, int t) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int m = (lo + hi) >>> 1;
            if (arr[m] <= t) lo = m + 1;
            else hi = m;
        }
        return lo;
    }

    // first index with arr[i] >= t
    private int lowerBound(int[] arr, int t) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int m = (lo + hi) >>> 1;
            if (arr[m] < t) lo = m + 1;
            else hi = m;
        }
        return lo;
    }
}

function fullBloomFlowers(flowers: number[][], queries: number[]): number[] {
    const starts: number[] = flowers.map(f => f[0]).sort((a, b) => a - b);
    const ends: number[] = flowers.map(f => f[1]).sort((a, b) => a - b);
    // upper_bound: first index with arr[i] > target
    const upperBound = (arr: number[], t: number): number => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (arr[m] <= t) lo = m + 1;
            else hi = m;
        }
        return lo;
    };
    // lower_bound: first index with arr[i] >= target
    const lowerBound = (arr: number[], t: number): number => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (arr[m] < t) lo = m + 1;
            else hi = m;
        }
        return lo;
    };
    const ans: number[] = [];
    for (const q of queries) {
        const started = upperBound(starts, q);
        const ended = lowerBound(ends, q);
        ans.push(started - ended);
    }
    return ans;
}