Максимальное количество домов, которые можно красить непрерывно, если указана продолжительность покраски и ограничение по дате.

Дан массив arr[][] , состоящий из N пар таких, что каждая пара {L, R} представляет собой i ^-й дом, который можно покрасить за L дней до R ^-го дня, задача состоит в том, чтобы найти максимальное количество домов которые можно красить непрерывно.
Примеры:

Input: N = 4, paint[ ][ ] = [[1, 19], [2, 2], [4, 17], [1, 1]]
Output: 3
Explanation: Maximum of three houses can be painted and order is {4, 3, 1} 

Input: N = 4, paint[ ][ ] = [[100, 210], [200, 1310], [1000, 1275], [2500, 3000]]
Output: 3

Подход: проблема может быть решена с использованием жадного подхода. Идея состоит в том, чтобы выбрать из наименьшего DaysRequired в текущем LastDay. Следуйте инструкциям ниже для подхода.

• Инициализируйте вектор, скажем, V, чтобы хранить все пары, которые можно взять.
• Отсортируйте вектор V , используя компаратор, пара.секунда меньше, чем пара.первый
• Инициализируйте приоритетную очередь pq и поместите первую пару вектора V.
• Инициализируйте переменную, скажем, t , чтобы сохранить время.
• Проходим вектор V и помещаем текущую пару в приоритетную очередь pq :
  • Если t+DaysRequired меньше или равно LastDay , продолжаем .
  • в противном случае извлеките из очереди приоритетов, сохраните в переменной temp и также обновите t равным t — temp.first
• Наконец, верните размер приоритетной очереди.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(NlogN)
Вспомогательное пространство: O(N)