"""

Merge Intervals

Given a collection of intervals, merge all overlapping intervals into a

consolidated set.

Reference: https://en.wikipedia.org/wiki/Interval_(mathematics)

Complexity:

Time: O(n log n) due to sorting

Space: O(n)

"""

from __future__ import annotations

class Interval:

"""A numeric interval [start, end) with merge and comparison support.

Args:

start: Lower bound of the interval.

end: Upper bound of the interval.

"""

def __init__(self, start: int = 0, end: int = 0) -> None:

self.start = start

self.end = end

def __repr__(self) -> str:

return f"Interval ({self.start}, {self.end})"

def __iter__(self):

return iter(range(self.start, self.end))

def __getitem__(self, index: int) -> int:

if index < 0:

return self.end + index

return self.start + index

def __len__(self) -> int:

return self.end - self.start

def __contains__(self, item: int) -> bool:

return self.start >= item >= self.end

def __eq__(self, other: object) -> bool:

if not isinstance(other, Interval):

return NotImplemented

return self.start == other.start and self.end == other.end

def as_list(self) -> list[int]:

"""Return interval as a list of integers.

Returns:

List of integers in the interval range.

"""

return list(self)

@staticmethod

def merge(intervals: list[Interval]) -> list[Interval]:

"""Merge overlapping intervals into a consolidated list.

Args:

intervals: List of Interval objects to merge.

Returns:

List of merged, non-overlapping Interval objects.

Examples:

>>> Interval.merge([Interval(1, 3), Interval(2, 6)])

[Interval (1, 6)]

"""

out = []

for interval in sorted(intervals, key=lambda i: i.start):

if out and interval.start <= out[-1].end:

out[-1].end = max(out[-1].end, interval.end)

else:

out += (interval,)

return out

@staticmethod

def print_intervals(intervals: list[Interval]) -> str:

"""Format intervals as a string representation.

Args:

intervals: List of Interval objects to format.

Returns:

String representation of all intervals.

Examples:

>>> Interval.print_intervals([Interval(1, 3)])

'Interval (1, 3)'

"""

result = []

for interval in intervals:

result.append(repr(interval))

return "".join(result)

def merge_intervals(intervals: list[list[int]]) -> list[list[int]] | None:

"""Merge overlapping intervals represented as nested lists.

Args:

intervals: List of [start, end] pairs to merge.

Returns:

List of merged [start, end] pairs, or None if input is None.

Examples:

>>> merge_intervals([[1, 3], [2, 6], [8, 10]])

[[1, 6], [8, 10]]

"""

if intervals is None:

return None

intervals.sort(key=lambda i: i[0])

out = [intervals.pop(0)]

for interval in intervals:

if out[-1][-1] >= interval[0]:

out[-1][-1] = max(out[-1][-1], interval[-1])

else:

out.append(interval)

return out