python 18 lines · 6 steps

How interval merging works

Sort intervals by start, then sweep once, extending or appending as overlaps appear.

Explained by highlit
Intermediate sorting greedy intervals single-pass
1from typing import List, Tuple
2 
3 
4def merge_intervals(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
5 if not intervals:
6 return []
7 
8 ordered = sorted(intervals, key=lambda pair: pair[0])
9 merged = [ordered[0]]
10 
11 for start, end in ordered[1:]:
12 last_start, last_end = merged[-1]
13 if start <= last_end:
14 merged[-1] = (last_start, max(last_end, end))
15 else:
16 merged.append((start, end))
17 
18 return merged
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Sorting by start point guarantees any overlap must involve the most recently kept interval.
  2. 2Extending an interval means taking the max of the two ends, since containment is possible.
  3. 3A single linear sweep after sorting resolves all merges without nested comparisons.

Related explainers

python 
from fastapi import APIRouter, BackgroundTasks, Depends, HTTPException, status
from pydantic import BaseModel, EmailStr
from sqlalchemy.orm import Session
 

Building a signup endpoint in FastAPI

dependency-injection request-validation background-tasks
Intermediate 8 steps
python 
from django import forms
from django.utils import timezone
 
from .models import Reservation

Multi-field validation in a Django ModelForm

form validation cross-field validation modelform
Intermediate 7 steps
python 
from django import template
from django.urls import reverse, NoReverseMatch
from django.utils.html import format_html
 

Active nav-link template tags in Django

template tags url routing active state
Intermediate 7 steps
python 
from functools import wraps
import asyncio
 
from fastapi import APIRouter, FastAPI, Request

Per-route request timeouts in FastAPI

decorators async timeouts
Intermediate 6 steps
python 
import os
from pathlib import Path
 
BASE_DIR = Path(__file__).resolve().parent.parent.parent

How a Django settings module is wired

configuration environment-variables middleware
Intermediate 8 steps
python 
def is_valid_card_number(number: str) -> bool:
    digits = [int(c) for c in number if c.isdigit()]
 
    if len(digits) < 13 or len(digits) > 19:

Validating card numbers with the Luhn check

checksum validation luhn-algorithm
Intermediate 6 steps

Share this explainer

Here's the card — post it anywhere.

How interval merging works — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code