let merge_intervals xs =
  let sorted = List.sort (fun (a, _) (b, _) -> a - b) xs in
  let rec aux acc cur xs =
    match xs with
    | [] -> List.rev (cur :: acc)
    | (s, e) :: rest ->
      let (cs, ce) = cur in
      if s <= ce then
        let new_e = if e > ce then e else ce in
        aux acc (cs, new_e) rest
      else
        aux (cur :: acc) (s, e) rest
  in
  match sorted with
  | [] -> []
  | h :: rest -> aux [] h rest

;;

let m = merge_intervals [(1, 3); (2, 6); (8, 10); (15, 18); (5, 9)] in
List.fold_left (fun acc (s, e) -> acc + e - s) 0 m
