Russian Doll Envelopes

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& env) {
        sort(env.begin(), env.end(), [](auto& a, auto& b) {
            return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
        });
        vector<int> tails;
        for (auto& e : env) {
            int h = e[1];
            auto it = lower_bound(tails.begin(), tails.end(), h);
            if (it == tails.end()) tails.push_back(h);
            else *it = h;
        }
        return tails.size();
    }
};

import "sort"

func maxEnvelopes(env [][]int) int {
    sort.Slice(env, func(i, j int) bool {
        if env[i][0] != env[j][0] {
            return env[i][0] < env[j][0]
        }
        return env[i][1] > env[j][1]
    })
    tails := []int{}
    for _, e := range env {
        h := e[1]
        idx := sort.SearchInts(tails, h)
        if idx == len(tails) {
            tails = append(tails, h)
        } else {
            tails[idx] = h
        }
    }
    return len(tails)
}

from bisect import bisect_left
from typing import List

class Solution:
    def maxEnvelopes(self, env: List[List[int]]) -> int:
        env.sort(key=lambda x: (x[0], -x[1]))
        tails: List[int] = []
        for _, h in env:
            idx = bisect_left(tails, h)
            if idx == len(tails):
                tails.append(h)
            else:
                tails[idx] = h
        return len(tails)

function maxEnvelopes(env) {
    env.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
    const tails = [];
    for (const [, h] of env) {
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (tails[mid] < h) lo = mid + 1;
            else hi = mid;
        }
        if (lo === tails.length) tails.push(h);
        else tails[lo] = h;
    }
    return tails.length;
}

class Solution {
    public int maxEnvelopes(int[][] env) {
        Arrays.sort(env, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        int[] tails = new int[env.length];
        int size = 0;
        for (int[] e : env) {
            int h = e[1];
            int lo = 0, hi = size;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < h) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = h;
            if (lo == size) size++;
        }
        return size;
    }
}

function maxEnvelopes(env: number[][]): number {
    env.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
    const tails: number[] = [];
    for (const [, h] of env) {
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (tails[mid] < h) lo = mid + 1;
            else hi = mid;
        }
        if (lo === tails.length) tails.push(h);
        else tails[lo] = h;
    }
    return tails.length;
}