Count requests in time ranges

EasyAbout 25 minProblem 1 of 3 in Binary searchDraft

The problem

A request log lists arrival times in seconds, sorted from earliest to latest; several requests can share a second.

Each entry of ranges is a pair [from, to]. For each pair, count the requests with from <= t < to, and return the counts in the same order as the ranges.

There can be as many ranges as requests, so count each range without walking the log.

  • 0 ≤ times.length ≤ 200,000, sorted, non-decreasing
  • 0 ≤ ranges.length ≤ 200,000
  • from ≤ to for every range

Examples

  1. countInRanges([1, 3, 3, 5, 8], [[3, 6]])returns [3]Seconds 3, 3 and 5.
  2. countInRanges([1, 3, 3, 5, 8], [[0, 1], [8, 9], [6, 8]])returns [0, 1, 0]A range never includes its end.
  3. countInRanges([], [[0, 100]])returns [0]

Hints

Hint 1 of 2

The count in [from, to) is (the first index with a time at least to) minus (the first index with a time at least from).

Hint 2 of 2

Write one function, the first index whose time is at least x, with lo = 0 and hi = times.length, and call it twice per range.

Editorial

Opens once you solve the problem, or after three checked attempts.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open