题解 | 信封嵌套问题

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

type email struct {
	w int
	h int
}

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		num, _ := strconv.Atoi(scanner.Text())
		if num == 0 {
			break
		}

		arr := make([]email, num)
		for i := 0; i < len(arr); i++ {
			scanner.Scan()
			w, _ := strconv.Atoi(scanner.Text())
			scanner.Scan()
			h, _ := strconv.Atoi(scanner.Text())

			arr[i] = email{w, h}

		}

		fmt.Println(process(arr))
	}
}

func process(arr []email) int {
	sort.Slice(arr, func(i, j int) bool {
		if arr[i].w == arr[j].w {
			return arr[i].h > arr[j].h // 高度需要从高到低，保证后续LIS问题求解时，严格递增
		}
		return arr[i].w < arr[j].w
	})

	h := make([]int, len(arr))
	for i := 0; i < len(arr); i++ {
		h[i] = arr[i].h
	}

	return LIS(h)
}

func LIS(arr []int) int {
	res := []int{}

	for _, v := range arr {
		l, r := 0, len(res)
		for l < r {
			mid := (r-l)/2 + l
			if res[mid] >= v {
				r = mid
			} else {
				l = mid + 1
			}
		}

		if l == len(res) {
			res = append(res, v)
		} else {
			res[l] = v
		}
	}
	return len(res)
}