Two Marks in Every Range

Hard

Ranges are given on the number line: ranges[i] = [a, b] covers all integers from a to b inclusive. Place marks at integer points so that every range contains **at least two** marks. Return the smallest possible number of marks.

Example 1

ranges=[[1, 4], [2, 6], [5, 8]] → 4

For example, marks 3, 4, 7, 8: [1, 4] contains 3 and 4, so does [2, 6], and [5, 8] contains 7 and 8. Three are not enough: [1, 4] and [5, 8] do not overlap and each needs two marks of its own.

Example 2

ranges=[[0, 5], [0, 5], [3, 4]] → 2

Marks 3 and 4 lie in all three ranges.

Example 3

ranges=[[1, 3], [3, 5]] → 3

Constraints

1 ≤ len(ranges) ≤ 5·10⁴
ranges[i] is a pair [a, b]
0 ≤ a < b ≤ 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Growing Capital Project by Project Hard Distinct Word Shorthands Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard Sorting Batches With Repeats Hard

Input

ranges=[[1, 4], [2, 6], [5, 8]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.