Как определить минимальное количество камер, чтобы охватить все здание?
Привет, люди. Мне нужен подход к этой проблеме на java.
Мы охранная компания и должны следить за зданием. Здание имеет форму правильного многоугольника, и в зависимости от количества камер, которые у нас есть, и поведения этих камер эта программа должна вычесть минимальное количество камер, чтобы покрыть все стены многоугольника.
Каждая из камер содержит два целых числа ai и bi, которые определяют количество стен, которые покрывают.
-если AI &ЛТ; Би то камера охватывает поскольку стена компа до стены би, который (Ай &ЛТ;= Дж &л;= би), то J = стенках крышки.
-если AI &ГТ; Би то камера охватывает поскольку стена компа до стены Н или крышки после падения Берлинской стены, 1 до стены би; это (Ма &ЛТ;= Дж &Л;= П), или (1 &ЛТ;= Дж &л;=би); к = стенках крышки.
Входные параметры таковы:
-n: количество стенок, и (3 <= n<= 10^6).
-k: количество камер, и (1 <= k <= 10^6)
- ai, bi для каждой камеры и (1 <= ai && bi <= n)
Процесс:
.
.
.
Выходные параметры таковы:
-минимальное количество камер.
Пример 1:
вход:
8 2
8 4
5 8
выход:
2
Пример 2:
вход:
100 7
1 50
50 70
70 100
90 40
20 60
60 80
80 20
выход:
3
ПД: извините за мой английский
Что я уже пробовал:
Я пытался думать в форме, чтобы правильно решить этот процесс, но мне нужна идея или подход.