rust 21 lines · 7 steps

Merging overlapping intervals in Rust

Sort intervals by start, then sweep once to fuse any that overlap into a single range.

Explained by highlit
Intermediate intervals sorting greedy in-place-mutation
1pub fn merge_intervals(mut intervals: Vec<(i64, i64)>) -> Vec<(i64, i64)> {
2 if intervals.is_empty() {
3 return Vec::new();
4 }
5 
6 intervals.sort_unstable_by_key(|&(start, _)| start);
7 
8 let mut merged: Vec<(i64, i64)> = Vec::with_capacity(intervals.len());
9 merged.push(intervals[0]);
10 
11 for &(start, end) in &intervals[1..] {
12 let last = merged.last_mut().unwrap();
13 if start <= last.1 {
14 last.1 = last.1.max(end);
15 } else {
16 merged.push((start, end));
17 }
18 }
19 
20 merged
21}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Sorting by start position guarantees that any overlap can be resolved by comparing only against the most recently kept interval.
  2. 2A single linear sweep after the sort is enough — no nested comparisons are needed.
  3. 3Mutating the last element in place via last_mut lets you extend a range without pushing a new entry.

Related explainers

rust 
use std::cmp::Ordering;
 
pub struct PrefixIndex {
    entries: Vec<String>,

Prefix search with binary partitioning in Rust

binary-search sorting case-insensitive
Intermediate 7 steps
rust 
use std::cmp::Ordering;
use std::str::FromStr;
 
#[derive(Debug, Clone, PartialEq, Eq)]

Parsing and ordering semantic versions in Rust

parsing trait-implementation ordering
Intermediate 8 steps
rust 
use axum::{
    extract::State,
    routing::{get, post, MethodRouter},
    Json, Router,

Self-documenting routes in Axum

builder-pattern closures shared-state
Intermediate 8 steps
rust 
use std::collections::HashMap;
use std::fs::File;
use std::io::{self, BufRead, BufReader};
use std::path::Path;

Parsing INI files in Rust

parsing file-io hashmap
Intermediate 9 steps
rust 
use axum::{
    extract::{Path, Query},
    http::Uri,
    response::{IntoResponse, Redirect},

Building HTTP redirect handlers in Axum

redirects extractors url-handling
Intermediate 7 steps
rust 
use axum::{
    body::Body,
    extract::MatchedPath,
    http::{Request, StatusCode},

An admin route guard in Axum middleware

middleware authorization request-extensions
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Merging overlapping intervals in Rust — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code