LIS applications: envelopes and chains

Several interview problems become a longest increasing subsequence (LIS) once the input is sorted the right way. The best known is nesting envelopes or boxes one inside another, often called Russian doll envelopes: sorted by width, a nest is a strictly rising run of heights, with one trap when widths are equal. A second is the longest chain of pairs, where each pair starts after the one before it ends, which a short greedy rule solves. A third counts how many longest runs there are, which matters when a leaderboard must say how many ways a best streak can happen.

Two problems: gift boxes and bookings

Problem A: nesting gift boxes. A shop keeps n flat gift boxes, box i of width w[i] and height h[i]. A box fits inside another when it is strictly narrower and strictly lower, and boxes are never turned. Return the largest number of boxes that can be nested one inside the next. Limits: 1 ≤ n ≤ 10⁵ and 1 ≤ w[i], h[i] ≤ 10⁹.

• [(30, 20), (40, 25), (40, 35), (25, 30), (50, 45), (35, 25)] gives 4: (30, 20) inside (35, 25) inside (40, 35) inside (50, 45).
• [(10, 10), (10, 20), (10, 30)] gives 1, because boxes of equal width never nest.

Problem B: a chain of bookings. A hall gets n bookings, each a pair (start, end) of whole hours with start < end. A chain lists bookings so that each starts strictly after the one before it ends. Return the length of the longest chain. Limits: 1 ≤ n ≤ 10⁵ and 0 ≤ start < end ≤ 10⁹.

• [(1, 4), (2, 3), (5, 8), (6, 7), (9, 10)] gives 3, for example 2 to 3, 6 to 7 and 9 to 10.
• [(3, 5), (1, 2), (2, 3)] gives 2, because a booking that starts in the hour another ends does not follow it.

The brute force, and why it fails at these sizes

For either problem, try every set of boxes or bookings and keep the largest set that sorts into a nest or a chain. The run below counts the sets: 256 for 8 boxes and 65,536 for 16, doubling with every box. At 100,000 boxes there are 2¹⁰⁰⁰⁰⁰ sets, a number with 30,103 digits. Comparing every pair of boxes instead still means about 5 × 10⁹ comparisons at that size, too many for a limit of a few seconds.

"""Both problems by brute force: try every set of boxes or bookings, and count the sets tried."""
import math


def fits(a, b):
    """Box a fits inside box b: strictly narrower and strictly lower (boxes are never turned)."""
    return a[0] < b[0] and a[1] < b[1]


def most_nested(boxes):
    best, tried = 0, 0
    for mask in range(1 << len(boxes)):
        tried += 1
        chosen = sorted(b for i, b in enumerate(boxes) if mask >> i & 1)
        if all(fits(x, y) for x, y in zip(chosen, chosen[1:])):
            best = max(best, len(chosen))
    return best, tried


def longest_chain(bookings):
    best, tried = 0, 0
    for mask in range(1 << len(bookings)):
        tried += 1
        chosen = sorted(p for i, p in enumerate(bookings) if mask >> i & 1)
        if all(x[1] < y[0] for x, y in zip(chosen, chosen[1:])):
            best = max(best, len(chosen))
    return best, tried


for boxes in ([(30, 20), (40, 25), (40, 35), (25, 30), (50, 45), (35, 25)], [(10, 10), (10, 20), (10, 30)]):
    best, tried = most_nested(boxes)
    print(f"boxes {boxes}: {best} nested, {tried} sets tried")
for bookings in ([(1, 4), (2, 3), (5, 8), (6, 7), (9, 10)], [(3, 5), (1, 2), (2, 3)]):
    best, tried = longest_chain(bookings)
    print(f"bookings {bookings}: a chain of {best}, {tried} sets tried")

print()
for n in (8, 12, 16):
    boxes = [(i, i) for i in range(n)]  # every set nests, the worst case for checking
    best, tried = most_nested(boxes)
    print(f"{n} boxes: {tried:,} sets tried")
digits = math.floor(100_000 * math.log10(2)) + 1
print(f"100,000 boxes: 2 ** 100000 sets, a number with {digits:,} digits")

boxes [(30, 20), (40, 25), (40, 35), (25, 30), (50, 45), (35, 25)]: 4 nested, 64 sets tried
boxes [(10, 10), (10, 20), (10, 30)]: 1 nested, 8 sets tried
bookings [(1, 4), (2, 3), (5, 8), (6, 7), (9, 10)]: a chain of 3, 32 sets tried
bookings [(3, 5), (1, 2), (2, 3)]: a chain of 2, 8 sets tried

8 boxes: 256 sets tried
12 boxes: 4,096 sets tried
16 boxes: 65,536 sets tried
100,000 boxes: 2 ** 100000 sets, a number with 30,103 digits

What to notice

• Sorted by width, a nest reads from left to right, and its heights rise strictly, so it is an increasing subsequence of the heights, as long as two boxes of the same width can never both be picked.
• A chain is ordered by its ends, and of all possible first bookings, the one that ends first leaves the most room for the rest.

Three methods follow. Sort-then-LIS orders the boxes by width and finds a longest strictly rising run of heights, with equal widths arranged so that they cannot chain. The greedy by end takes the booking that ends first, then each booking that starts after the last one taken ends. Counting keeps, beside each run length, how many runs reach it, and a Fenwick tree finds those counts quickly.

Boxes: sort by width, then a rising run of heights Pro: opens with a Pro, Premium or Ultimate pass