# 2250. Count Number of Rectangles Containing Each Point
###### tags: `Leetcode` `Medium` `Binary Search`
Link: https://leetcode.com/problems/count-number-of-rectangles-containing-each-point/description/
## 思路
一开始想到用双指针 但后来发现不行 因为[1,100]可能不能fit进某个rectangle里面，但并不代表[2,5]fit不进去，也不能代表[0,5]fit不进去

由于h的范围是从0-100，所以我们可以遍历所有h 所以我们把所有rectangle按照h分类
对于每个点来说我们只需要看height>=这个point的h的所有rectangle就可以
在每一类里我们用binary search找到一共有多少个合适的l 加在一起就是答案
## Code

class Solution {
    public int[] countRectangles(int[][] rectangles, int[][] points) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int[] r:rectangles){
            int l = r[0], h = r[1];
            if(!map.containsKey(h)) map.put(h, new ArrayList<>());
            map.get(h).add(l);
        }
        for(int key:map.keySet()) Collections.sort(map.get(key));
        int[] ans = new int[points.length];
        for(int i=0; i<points.length; i++){
            int[] point = points[i];
            for(int j=point[1]; j<=100; j++){
                if(map.get(j)!=null) ans[i] += binarySearch(point[0], map.get(j));
            }
        }
        return ans;
    }
    private int binarySearch(int l, List<Integer> list){
        int start = 0, end = list.size();
        while(start<end){
            int mid = start+(end-start)/2;
            if(list.get(mid)<l) start = mid+1;
            else end=mid;
        }
        return list.size()-start;
    }
}