Back to problems

Streaming Interval Coverage on a Number Axis

Algorithm · Waymo · Hard

Requirements Represent the polluted portion of a real-valued axis spanning [0, 50]. Provide the function bool ingest(double point). Each invocation adds pollution across the interval from point - 0.5 through point + 0.5. Pollution is permanent: once any part of the axis is covered, it remains covered. ingest must return true exactly when the complete interval [0, 50] has become polluted; before that, it returns false. New pollution ranges can overlap existing ranges or be…

Checking your access…