406. Queue Reconstruction by Height

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) ->(a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
        int n = people.length;
        List<int[]> list = new ArrayList<>();
        for(int i = n - 1; i >= 0; i--)
        {
            int pos = binarySearch(list, people[i]);
            // System.out.println(pos);
            list.add(pos, people[i]);
        }
        int[][] re = new int[n][];
        for(int i = 0; i < n; i++) re[i] = list.get(i);
        return re;
    }

    int binarySearch(List<int[]> list, int[] p)
    {
        int n = list.size();
        if(n < 1) return 0;
        int lo = 0, hi = n - 1;
        while(lo < hi)
        {
            int m = (lo + hi) / 2;
            if(m < p[1]) lo = m + 1;
            else hi = m;
        }
        if(lo < p[1]) lo++;
        return lo;
    }
}