java 22 lines · 7 steps

Merging overlapping intervals in Java

Sort intervals by start, then sweep once, extending or opening ranges as you go.

Explained by highlit

Intermediate intervals sorting greedy arrays

1public List<int[]> merge(int[][] intervals) {
  if (intervals.length == 0) {
      return new ArrayList<>();
  }
5 
  Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
7 
  List<int[]> merged = new ArrayList<>();
  int[] current = intervals[0].clone();
  merged.add(current);
11 
  for (int[] interval : intervals) {
      if (interval[0] <= current[1]) {
          current[1] = Math.max(current[1], interval[1]);
      } else {
          current = interval.clone();
          merged.add(current);
      }
  }
20 
  return merged;
22}

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1Sorting by start makes overlaps detectable with a single left-to-right pass.
2Overlap means the next start is within the current range's end, so extend rather than append.
3Cloning the interval you add lets you mutate the running range without corrupting the input.

Related explainers

java

public interface GitHubClient {
 
    @GetExchange("/users/{username}")
    GitHubUser getUser(@PathVariable String username);

Declarative HTTP clients in Spring

http-client declarative-api proxy

Intermediate 8 steps

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Building a trie for autocomplete in Java

trie prefix-tree recursion

Intermediate 8 steps

java

@RestController
@RequestMapping("/api/products")
public class ProductSearchController {

Binding collection query params in Spring

rest-api query-parameters dependency-injection

Intermediate 6 steps

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

Evaluating math expressions with two stacks

stacks parsing operator-precedence

Intermediate 9 steps

java

@Entity
@Table(name = "orders")
@SQLDelete(sql = "UPDATE orders SET deleted = true, deleted_at = now() WHERE id = ?")
@Where(clause = "deleted = false")

Soft deletes with Hibernate in Spring

soft-delete jpa hibernate

Intermediate 9 steps

java

@GetMapping("/files/{id}")
public ResponseEntity<StreamingResponseBody> download(
        @PathVariable String id,
        @RequestHeader(value = HttpHeaders.RANGE, required = false) String rangeHeader) throws IOException {