#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Interval {
pub start: i64,
pub end: i64,
}
impl Interval {
pub fn new(start: i64, end: i64) -> Option<Interval> {
if end < start {
return None;
}
Some(Interval { start, end })
}
pub fn overlaps_or_touches(&self, other: &Interval) -> bool {
// half-open ranges: touching at a boundary does not overlap
other.start < self.end
}
pub fn merge_with(&mut self, other: &Interval) {
if other.end > self.end {
self.end = other.end;
}
}
}use crate::interval::Interval;
pub fn merge_intervals(intervals: &[Interval]) -> Vec<Interval> {
if intervals.is_empty() {
return Vec::new();
}
let mut sorted = intervals.to_vec();
sorted.sort_by_key(|iv| iv.start);
let mut merged: Vec<Interval> = Vec::with_capacity(sorted.len());
let mut current = sorted[0];
for iv in sorted.into_iter().skip(1) {
if current.overlaps_or_touches(&iv) {
current.merge_with(&iv);
} else {
merged.push(current);
current = iv;
}
}
merged.push(current);
merged
}use crate::interval::Interval;
use crate::merge::merge_intervals;
fn iv(start: i64, end: i64) -> Interval {
Interval::new(start, end).expect("valid interval")
}
#[test]
fn merges_overlapping_bookings() {
let input = vec![iv(9, 11), iv(10, 12), iv(15, 16)];
let out = merge_intervals(&input);
assert_eq!(out, vec![iv(9, 12), iv(15, 16)]);
}
#[test]
fn keeps_back_to_back_bookings_separate() {
let input = vec![iv(9, 10), iv(10, 11)];
let out = merge_intervals(&input);
assert_eq!(out, vec![iv(9, 10), iv(10, 11)]);
}
#[test]
fn handles_contained_and_unsorted() {
let input = vec![iv(13, 20), iv(9, 12), iv(14, 15)];
let out = merge_intervals(&input);
assert_eq!(out, vec![iv(9, 12), iv(13, 20)]);
}
#[test]
fn rejects_malformed_interval() {
assert!(Interval::new(10, 5).is_none());
}This snippet shows how a booking schedule is collapsed into a set of non-overlapping busy blocks, a common step before rendering availability or detecting double-bookings. The core idea is the interval-merge algorithm: sort intervals by start time, then walk them once, extending the current block whenever the next interval starts before the current one ends.
The Interval type tab defines a half-open range [start, end) over i64 timestamps (Unix seconds work well). Using a half-open convention matters because two bookings where one ends exactly when the next begins are adjacent, not overlapping, and should stay separate. The overlaps_or_touches method encodes the merge threshold, and merge_with widens the block by taking the maximum end so a short booking nested inside a longer one does not accidentally shrink it.
The merge module tab holds the algorithm itself. merge_intervals first guards the empty case, then sorts a cloned vector by start using sort_by_key. The single pass keeps a mutable current block; each following interval either merges into current via merge_with or is pushed and becomes the new current. Sorting is O(n log n) and dominates the linear scan, which is the standard cost for this problem. Cloning the input keeps the function non-destructive, a reasonable trade-off unless the caller owns a large vector and can afford to sort in place.
A subtle pitfall handled here: because intervals are sorted by start only, the running current.end can exceed the next interval's end, so merge_with must guard with max rather than blindly assigning. Malformed intervals where end < start are rejected by Interval::new returning an Option, keeping bad data out of the merge entirely.
The tests tab exercises the tricky boundaries: fully contained intervals, back-to-back bookings that must not merge, and unsorted input. These cases are where naive implementations usually break, so pinning them down protects against regressions when the algorithm is later optimized.
Related snips
class CommentsController < ApplicationController
before_action :set_post
def create
@comment = @post.comments.build(comment_params)System test: asserting Turbo Stream responses
struct Config<'a> {
name: &'a str,
value: &'a str,
}
fn parse_config(line: &str) -> Config {Lifetime annotations for flexible borrowing in structs
use crossbeam::channel::unbounded;
use std::thread;
fn main() {
let (tx, rx) = unbounded();Crossbeam for advanced concurrent data structures
use tracing::{info, instrument};
#[instrument]
fn process_request(user_id: u64) {
info!(user_id, "Processing request");
// Work happens heretracing for structured logging and distributed tracing
use std::sync::mpsc;
use std::thread;
fn main() {
let (tx, rx) = mpsc::channel();Channels (mpsc) for message passing between threads
use clap::Parser;
#[derive(Parser, Debug)]
#[command(author, version, about)]
struct Args {
#[arg(short, long)]clap for CLI argument parsing with derive macros
Share this code
Here's the card — post it anywhere.
