Functional Programming in Python, Part II: Intervals

Intervals

This is a continuation of my series on Python programming from a functional perspective. In the first post we looked at sliding window problems, here we’ll deal with intervals.

Can Attend Meetings

def can_attend(intervals: list[int, int]) -> bool:
    meetings = sorted(intervals)
    return all(a[1] <= b[0] for a, b in zip(meetings, meetings[1:]))

meetings = [(1, 3), (4, 6), (5, 7), (7, 10), (11, 12)]
can_attend(meetings)

False

Interlude: Python’s reduce()

from functools import reduce

nums = [1, 2, 3, 4 ,5]

# Classics for reference
sum_ = reduce(lambda acc, x: acc + x, nums)
product = reduce(lambda acc, x: acc * x, nums)
maximum = reduce(lambda acc, x: max(acc, x), nums)
minimum = reduce(lambda acc, x: min(acc, x), nums)

# Flattening, actually useful
nested = [[1, 2], [3, 4], [5, 6]]
flatten = reduce(lambda acc, x: acc + x, nested)

# Counting occurrences
words  = ["a", "b", "a", "c", "b", "a"]

# Merging intervals

# Pipeline of functions

Insert Interval

from functools import reduce

def insert_interval(intervals: list[tuple[int, int]], interval: tuple[int, int]) -> list[tuple[int, int]]:
    meetings = sorted(intervals)
    before = [m for m in meetings if m[1] <= interval[0]]
    overlap = [m for m in meetings if m[0] <= interval[1] and m[1] > interval[0]]
    after = [m for m in meetings if m[0] > interval[1]]

    merged = reduce(
        lambda acc, iv: [min(acc[0], iv[0]), max(acc[1], iv[1])],
        overlap,
        interval
    )

    return before + [merged] + after

intervals = [[1,3],[6,9]]
newInterval = [2,5]
insert_interval(intervals, newInterval)

[[1, 5], [6, 9]]

Interlude: permutations

def permutations(nums: list[int]):
    if not nums:
        yield []
        return
    for i, x in enumerate(nums):
        for rest in permutations(nums[:i] + nums[i+1:]):
            yield [x] + rest

list(permutations([1,2,3]))

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]