Fewest Inspection Points

MediumIntervals

Problem

A pipeline runs along a straight line. Each entry of segments is [from, to], a stretch of pipe (both ends included) that must be inspected at least once. An inspector placed at integer position p inspects every segment with from ≤ p ≤ to.

Return the minimum number of inspectors needed so that every segment is inspected.

Example 1

Input:
segments = [[10, 16], [2, 8], [1, 6], [7, 12]]
Output:
2

An inspector at 6 covers [2, 8] and [1, 6]; one at 12 covers [10, 16] and [7, 12].

Example 2

Input:
segments = [[1, 2], [2, 3], [3, 4], [4, 5]]
Output:
2

Inspectors at 2 and 4 suffice.

Constraints

  • 1 ≤ segments.length ≤ 10^5
  • -2^31 ≤ from ≤ to ≤ 2^31 - 1

Hint

Show the first hint

Look at the segment that ends first. Some inspector must sit inside it. Where is the best place for that inspector?

Walkthrough

How to approach it

01Clarify before coding

  • Are both ends included? Yes, an inspector exactly at to counts.
  • Can values reach the 32-bit limits? Yes; avoid sentinels like lastPoint + 1 that could overflow in fixed-width languages.
  • Can segments be single points? Yes, from = to.

02Brute force

Try placing k inspectors at every combination of segment endpoints for k = 1, 2, ... until all segments are covered.

Cost: Exponential in the number of segments.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.