leetcode-go/leetcode/hard/354.russian-doll-envelopes.go

type nx2arr [][]int

func (arr nx2arr) Len() int { return len(arr) }
func (arr nx2arr) Less(i, j int) bool {
	if arr[i][0] != arr[j][0] {
		return arr[i][0] < arr[j][0]
	} else {
		return arr[j][1] < arr[i][1] // If the width is the same, the tallest is in front
	}
}
func (arr nx2arr) Swap(i, j int) { arr[i], arr[j] = arr[j], arr[i] }

func maxEnvelopes(envelopes [][]int) (n int) { // Just like "the longest increasing substring"
	sort.Sort(nx2arr(envelopes))
	queue := make([][]int, 0)
	for i := range envelopes {
		beg, end := 0, n-1
		for beg <= end {
			mid := beg + (end-beg)/2
			if queue[mid][1] < envelopes[i][1] { // Binary search with duplicates
				beg = mid + 1
			} else if envelopes[i][1] <= queue[mid][1] {
				end = mid - 1
			}
		}
		if beg == n {
			queue = append(queue, envelopes[i])
			n++
		} else {
			queue[beg] = envelopes[i]
		}
	}
	return
}