Design calendar event conflict handling

01The design, in the six-step framework

1. Requirements and use cases

This question often starts as a coding exercise (insert an interval, detect a clash) and then widens into "how would this sit inside a calendar product". The design below is built so the coding core survives the widening.

• A user creates an event with a start, an end and a time zone, and is told immediately if it clashes with an existing event on the same calendar.
• A user edits an event; two people editing the same event from two devices must not silently overwrite each other.
• A user creates a recurring event (daily, weekly, every n days) with an optional end date, and can cancel one occurrence.
• The calendar answers "what is on between these two instants" and "is this range free".
• For a group of calendars, the system finds the first slot of a given length when everyone is free.

Out of scope: invitations and attendee responses, reminders, storage. Non-functional constraints: the clash check must be logarithmic in the number of events; recurrence must never be materialised without a bound; an edit that lost a race must fail loudly with the current version attached.

2. Core entities and relationships

• Interval: a half-open pair of UTC instants with overlaps; the only place the boundary rule lives.
• Event: an immutable record (title, interval, zone, recurrence, exceptions) plus a version integer.
• Recurrence: a rule that expands to concrete occurrences inside a requested window, never beyond it.
• Calendar: owns the events of one user, keeps a sorted index of single occurrences and a separate list of recurring events.
• ConflictPolicy: a specification saying what counts as a clash (hard overlap, or also "travel time" gaps).
• Scheduler: the group operation that intersects free time across calendars.

A calendar composes its events; an event composes its interval. The recurrence is aggregated because the same rule object ("every Monday") can be shared by many events, and the policy is aggregated because it is configuration, not state.

3. Interfaces and key methods

from dataclasses import dataclass, replace
from typing import Optional, FrozenSet

@dataclass(frozen=True)
class Interval:
    start: int
    end: int
    def overlaps(self, other: "Interval") -> bool:
        return self.start < other.end and other.start < self.end
    def length(self) -> int:
        return self.end - self.start

@dataclass(frozen=True)
class Recurrence:
    every_seconds: int
    until: Optional[int] = None
    def __post_init__(self) -> None:
        if self.every_seconds <= 0:
            raise ValueError("a recurrence must step forward")
    def expand(self, first: Interval, window: Interval) -> list:
        """Occurrences of `first` repeated every `every_seconds` that overlap `window`; bounded by the window."""

@dataclass(frozen=True)
class Event:
    id: str
    interval: Interval
    zone: str
    recurrence: Optional[Recurrence] = None
    exceptions: FrozenSet[int] = frozenset()   # occurrence starts that were cancelled
    version: int = 1

class VersionConflict(Exception):
    """Raised when expected_version is stale; carries the current event."""

class Calendar:
    def create(self, event: Event) -> Event:
        """Reject if any occurrence clashes under the policy."""
    def update(self, event_id: str, expected_version: int, **changes) -> Event:
        """Compare-and-set on version; re-checks clashes for the new shape."""
    def occurrences(self, window: Interval) -> list:
        """Concrete (event, interval) pairs inside the window, sorted by start."""
    def is_free(self, interval: Interval) -> bool:
        """True if nothing on this calendar clashes with the interval."""

Invariants: singles stays sorted by start so is_free is a bisect plus two neighbour checks; an Event is never mutated, update produces a new one with version + 1; expand never returns an occurrence outside the window, so no query can run away on an endless series.

4. Design patterns and the choices behind them

Optimistic concurrency instead of locks on edits

The force: two devices edit one event; the edit takes seconds of human time, so holding a lock is wrong. Each event carries a version; update succeeds only if the caller's expected_version matches, otherwise it raises VersionConflict with the current event so the client can merge. That is optimistic concurrency, and it is the answer interviewers want when they contrast it with pessimistic locking. The in-process lock in the code protects only the few microseconds of the compare-and-set itself.

Immutable events

The force: recurring expansion, clash checks and listings all read events while updates happen. Making Event a frozen value object means a reader holding an event can never see it change under it, and replace gives cheap new versions. The alternative, mutating fields in place, forces every reader to lock.

Clash rule as a specification

The force: "overlap" is the first rule; "15 minutes of travel time between locations" is the second. ConflictPolicy is a specification with one method, so the calendar never hard-codes the rule. Interval arithmetic stays in Interval; the policy decides how much padding to add before asking.

5. Core flow and code

1. Calendar.create receives the event in UTC instants; the zone travels with it for display.
2. If the event recurs, Recurrence.expand produces its occurrences within a bounded horizon; otherwise the single interval is the list.
3. For each occurrence the calendar checks singles by bisect, then every recurring event by expanding it over the occurrence only, widened by the policy's gap so a nearby occurrence is still seen.
4. On success the event is inserted (sorted list for singles, plain list for recurring) under the lock.
5. update repeats the check for the proposed new shape, excluding the event being edited, then swaps versions atomically.

import bisect, threading
from dataclasses import dataclass, replace
from typing import Optional

class HardOverlapPolicy:
    gap = 0
    def clashes(self, a: Interval, b: Interval) -> bool:
        return a.overlaps(b)

class TravelTimePolicy:
    def __init__(self, gap_seconds: int):
        self.gap = gap_seconds
    def clashes(self, a: Interval, b: Interval) -> bool:
        padded = Interval(a.start - self.gap, a.end + self.gap)
        return padded.overlaps(b)

def _expand(rec: Recurrence, first: Interval, window: Interval) -> list:
    out, length, step = [], first.length(), rec.every_seconds
    if window.end <= first.start:
        return out
    k = max(0, (window.start - first.end) // step + 1)   # first occurrence that can touch the window
    start = first.start + k * step
    while start < window.end and (rec.until is None or start <= rec.until):
        occ = Interval(start, start + length)
        if occ.overlaps(window):
            out.append(occ)
        start += step
    return out

Recurrence.expand = _expand

class Calendar:
    HORIZON = 366 * 24 * 3600   # recurring events are checked one year ahead

    def __init__(self, policy=None):
        self.singles: list = []        # sorted by interval.start
        self.recurring: list = []
        self.policy = policy or HardOverlapPolicy()
        self._by_id: dict = {}
        self._lock = threading.Lock()

    def _occs(self, event: Event, window: Interval) -> list:
        if event.recurrence is None:
            return [event.interval] if event.interval.overlaps(window) else []
        return [o for o in event.recurrence.expand(event.interval, window) if o.start not in event.exceptions]

    def _clash(self, interval: Interval, skip_id: Optional[str] = None) -> Optional[Event]:
        i = bisect.bisect_left(self.singles, interval.start, key=lambda e: e.interval.start)
        for j, step in ((i - 1, -1), (i, 1)):      # the nearest neighbour on each side is the only candidate
            if 0 <= j < len(self.singles) and self.singles[j].id == skip_id:
                j += step                          # the event being edited does not count
            if 0 <= j < len(self.singles) and self.policy.clashes(self.singles[j].interval, interval):
                return self.singles[j]
        reach = Interval(interval.start - self.policy.gap, interval.end + self.policy.gap)
        for e in self.recurring:
            if e.id != skip_id and any(self.policy.clashes(o, interval) for o in self._occs(e, reach)):
                return e
        return None

    def _check(self, event: Event, skip_id: Optional[str] = None) -> None:
        if event.recurrence is not None and event.recurrence.every_seconds < event.interval.length():
            raise ValueError("occurrences of this event overlap each other")
        horizon = Interval(event.interval.start, event.interval.start + self.HORIZON)
        for occ in self._occs(event, horizon):
            other = self._clash(occ, skip_id)
            if other is not None:
                raise ValueError(f"clashes with {other.id}")

    def create(self, event: Event) -> Event:
        with self._lock:
            self._check(event)
            self._insert(event)
            return event

    def _insert(self, event: Event) -> None:
        if event.recurrence is None:
            bisect.insort(self.singles, event, key=lambda e: e.interval.start)
        else:
            self.recurring.append(event)
        self._by_id[event.id] = event

    def update(self, event_id: str, expected_version: int, **changes) -> Event:
        with self._lock:
            current = self._by_id[event_id]
            if current.version != expected_version:
                raise VersionConflict(current)
            proposed = replace(current, version=current.version + 1, **changes)
            self._check(proposed, skip_id=event_id)
            self.singles = [e for e in self.singles if e.id != event_id]
            self.recurring = [e for e in self.recurring if e.id != event_id]
            self._insert(proposed)
            return proposed

    def is_free(self, interval: Interval) -> bool:
        with self._lock:
            return self._clash(interval) is None

    def occurrences(self, window: Interval) -> list:
        with self._lock:
            out = [(e, o) for e in self.singles + self.recurring for o in self._occs(e, window)]
            return sorted(out, key=lambda p: p[1].start)

class Scheduler:
    def first_free(self, calendars: list, length: int, window: Interval, step: int = 900) -> Optional[Interval]:
        t = window.start
        while t + length <= window.end:
            cand = Interval(t, t + length)
            if all(c.is_free(cand) for c in calendars):
                return cand
            t += step
        return None

Cancelling one occurrence is an update that adds its start instant to exceptions; the expansion skips it, and because the event is immutable the cancellation is itself versioned. This version steps in fixed seconds, so a weekly event holds its UTC time and its local time moves by an hour when the clocks change. Keeping the wall time would mean a rule that stores local time and the zone, with expand converting each occurrence separately, which is why the zone stays a field on the event rather than being dropped at creation.

6. Extensions, concurrency and what interviewers probe

• "Days when everyone is free" and "at least P people free": run a sweep over all occurrences as +1/−1 events sorted by time; the count tells you how many are busy at each instant, which answers both questions in one pass, the merge-intervals family the reports mention.
• "Optimistic versioning or locking?" Versions for human-speed edits, a short lock only around the compare-and-set; say that a lost race returns the fresh event so the client can show a merge dialog.
• "Recurring forever": never materialise; expand is bounded by the window and the clash check by HORIZON. State the horizon as an assumption out loud.
• Free/busy index: at scale, keep a precomputed busy list per day so first_free stops probing in 15-minute steps; the policy object stays the same.
• Test first: back-to-back events are free; an occurrence cancelled by exception no longer blocks; a stale version raises VersionConflict.
• Common mistake: expanding recurrences for the clash check over all time, or storing local wall time without the zone and getting a different answer after the clocks change.

02Where this question was reported

• LeetCode Discuss · LeetCode 729 (Medium), Google-tagged, freq 27.4; 731 My Calendar II freq 24.5
• LeetCode Discuss · Round 1: code a calendar scheduler, then discuss how that piece fits into a larger calendar application
• ReturnZero · Merge-intervals family: merged calendar view -> insert interval -> intersect two schedules -> when everyone is free
• LeetCode Discuss · Calendar of N people: days when all free; follow-up days when at least P are free
• PracHub · Google onsite: overlap predicate, recurrence, time zones/DST, optimistic versioning vs locking, free/busy index