Minimum Cameras to Watch the Whole Circle Problem

Minimum Cameras to Watch the Whole Circle Problem — ExecCode Hard DSA Practice

Solve the Minimum Cameras to Watch the Whole Circle problem on ExecCode. Free online hard DSA practice in Two Pointers. Write and run code in Java, C++, Python — no signup required to run.

Problem description

There are n positions numbered from 1 to n around a circle. Each camera is represented by [start, end] and watches every position on the inclusive clockwise arc from start to end. When start end, the arc wraps through position n and continues at position 1. For example, [8, 2] when n = 10 watches positions 8, 9, 10, 1, 2. Choose the minimum number of cameras whose combined watched arcs cover every position on the circle. Return -1 if this is impossible. You are given: n — the number of positions on the circle cameras — a list of inclusive arcs [start, end] For example, when n = 8, cameras [8, 4] and [5, 7] cover the whole circle, so the answer is 2. A camera may itself cover the full circle: [6, 5] when n = 10 has answer 1. Return the minimum number of cameras required, or -1 if full coverage is impossible.

Examples

Input {'n': 12, 'cameras': [[1, 5], [4, 8], [7, 10], [9, 12], [2, 6]]}; Output 3. Input {'n': 10, 'cameras': [[6, 5]]}; Output 1. Input {'n': 8, 'cameras': [[8, 4], [5, 7]]}; Output 2

Constraints

1 <= n <= 100000\n- 1 <= cameras.length <= 100000\n- 1 <= cameras[i][0], cameras[i][1] <= n\n- Each camera may be selected at most once\n- Camera arcs and their endpoints are inclusive

Practice Minimum Cameras to Watch the Whole Circle free on ExecCode. Browse DSA problems, topic map, and placement guides.