Merge Overlapping Ranges with a NamedTuple

A calendar stores each meeting as a range of minutes, such as 540 to 600 for 9:00 to 10:00. Some meetings overlap. To show when someone is busy, you merge every group of ranges that overlap or touch.

solve([[7, 9], [1, 3], [3, 5]], 4)
# {
#     "merged": [Interval(1, 5), Interval(7, 9)],
#     "contains": [True, False],
#     "tuple_equality": True,
#     "cross_type_equality": True,
#     "same_kind": False,
# }

A NamedTuple suits a range, because sorted already orders tuples by lo and then by hi.

Complete Interval

Keep Interval as a typing.NamedTuple with the fields lo: int and hi: int, in that order. Every input has lo <= hi. Negative numbers and ranges where lo == hi are valid. Add three methods:

• overlaps(other: Interval) -> bool returns True when the two ranges share at least one point. The ranges are closed, which means they include both ends, so sharing only an endpoint counts.
• merge(other: Interval) -> Interval returns the range from the smaller lo to the larger hi. It does this even for ranges that do not overlap, so merge_all must check overlaps first.
• __contains__(point: object) -> bool returns isinstance(point, int) and lo <= point <= hi. This replaces the tuple rule, where 3 in (1, 5) is False because 3 is not an item. A float such as 3.0 gives False. True and False count as 1 and 0, because bool is a subclass of int.

Python refuses to create a NamedTuple class whose methods use zero-argument super() or the name __class__, so leave both out.

Write the helpers

• same_kind(a, b) returns type(a) is type(b), which checks the exact class and ignores the contents.
• merge_all(intervals) takes any Iterable[Interval] and returns a new list[Interval]. Sort by lo, then hi, and merge every group of ranges that overlap or touch. The input may be a generator, so read it only once and do not index it. Leave an input list unchanged.

Edge cases

• [1, 2] and [2, 5] touch, so they merge into [1, 5].
• [1, 2] and [3, 4] stay separate. They share no point, even though no integer lies between them.
• A range inside another range, or a repeated range, joins its group.
• An empty input returns an empty list.

What solve returns

solve(intervals, probe) takes a list of [lo, hi] lists and an integer probe. It builds Interval objects, calls merge_all, and returns:

Put the Interval objects in a plain list. The grader reads each one as a tuple, and a list of lists does not match. The last three keys are the same for every input, including an empty one.

The last three keys repeat a point from the article Choose Between a Dataclass, NamedTuple and TypedDict. Interval(1, 2), Span(1, 2) and (1, 2) are equal and have equal hashes, so only same_kind tells them apart.

Keep the supplied cross_type_equality helper. It calls operator.eq because mypy rejects Interval(1, 2) == Span(1, 2). Your code must pass mypy --strict.