Nesting Envelopes
Problem
Each envelope is given as [width, height]. One envelope fits inside another only when it is strictly narrower and strictly shorter; rotating is not allowed. Return the largest number of envelopes you can nest one inside the next. The list may hold up to 100,000 envelopes, so a quadratic comparison of every pair is too slow.
Examples
Input: envelopes = [[4, 5], [4, 6], [6, 7], [2, 3], [1, 1]]
Output: 4
Why: [1, 1] inside [2, 3] inside [4, 5] inside [6, 7]Input: envelopes = [[3, 3], [3, 3]]
Output: 1
Why: identical envelopes cannot hold each otherInput: envelopes = []
Output: 0
Why: edge case, nothing to nestHints
0 / 3
Sorting by width turns the problem into picking a rising sequence of heights. The catch is envelopes with the same width, which must never both be picked.
If envelopes of equal width are sorted by height from tallest to shortest, no strictly rising run of heights can contain two of them.
After that sort, find the longest strictly rising run of heights in O(n log n): keep a list where entry k is the smallest height that can end a nest of k + 1 envelopes, and for each height, binary search the first entry that is not smaller, replacing it or appending.
Solution
Sorting by width leaves only heights to compare, except that equal widths must not chain, so ties are sorted by height descending, which makes two of them impossible in one strictly rising run. The answer is then the longest strictly rising subsequence of the heights. The patience method keeps tails, where tails[k] is the smallest height that can finish a nest of length k + 1; each height replaces the first tail that is not smaller, found by binary search, or extends the list. Time is O(n log n) and space is O(n).
from bisect import bisect_left
def max_nesting(envelopes):
# equal widths cannot nest, so the tallest of them goes first
order = sorted(envelopes, key=lambda e: (e[0], -e[1]))
tails = [] # tails[k] = smallest last height of a nest of k + 1
for _, h in order:
k = bisect_left(tails, h) # first tail that is not smaller than h
if k == len(tails):
tails.append(h) # h extends the longest nest
else:
tails[k] = h # same length, lower finish
return len(tails)
print(max_nesting([[4, 5], [4, 6], [6, 7], [2, 3], [1, 1]])) # -> 4
print(max_nesting([[3, 3], [3, 3]])) # -> 1
print(max_nesting([])) # -> 0Stuck on the idea rather than the code? LIS in O(n log n) covers it.