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 serde::Deserialize;
 
#[derive(Debug, Deserialize)]
#[serde(untagged)]

Parsing flexible JSON shapes with serde

deserialization enums json
Intermediate 6 steps
rust 
use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;
use std::fs::File;
use std::io::{self, BufRead, BufReader, BufWriter, Lines, Write};

K-way merge of sorted logs in Rust

binary-heap k-way-merge streaming-io
Intermediate 8 steps
rust 
use axum::{
    extract::{Path, State},
    response::sse::{Event, KeepAlive, Sse},
};

Streaming import progress with SSE in Axum

server-sent-events streams watch-channel
Advanced 7 steps
rust 
use std::f64::consts::PI;
 
#[derive(Debug, Clone, Copy)]
pub struct LatLng {

Building geographic bounding boxes in Rust

geospatial value-types option
Intermediate 7 steps
rust 
use chrono::{Duration, NaiveDate};
 
#[derive(Debug)]
pub struct DateRange {

Parsing and iterating date ranges in Rust

error-handling iterators parsing
Intermediate 7 steps
rust 
use std::collections::VecDeque;
use std::sync::{Arc, Condvar, Mutex};
use std::time::{Duration, Instant};
 

Building a counting semaphore in Rust

concurrency synchronization condition-variable
Advanced 9 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