Проверьте, будет ли ЦП успешно обрабатывать данные запросы или нет.

Учитывая целочисленную емкость , максимальное количество процессов, обрабатываемых ЦП в любой момент времени, и задан запрос двумерного массива[][] , каждый запрос имеет три параметра:

• ряд процессов, требующих CPU,
• время начала,
• время окончания.

Задача состоит в том, чтобы проверить, будет ли ЦП успешно обрабатывать все запросы или нет. Если да, верните TRUE, иначе FALSE. Начальное время CPU изначально равно 0.

Примеры:

Input: request[][] = {{2, 1, 5}, {3, 3, 7}}, capacity = 4
Output: false
Explanation: First request says that 2 processes need CPU at time=1 and will release back at time=5. CPU servicing 2 process at time=1. Second request comes and asks CPU to service 3 more processes at time=3 to time=7. At time=3, CPU is busy with request-1 and hence can’t service request-2. So, return FALSE.

Input: request[][] = {{2, 1, 5}, {3, 3, 7}}, capacity = 5
Output: true

Подход . Идея состоит в том, чтобы отслеживать загрузку ЦП в каждый момент времени. Если загрузка ЦП превышает максимальный предел, остановите программу с возвратом FALSE. Пусть curr будет количеством процессов, находящихся в настоящее время в процессоре. Итак, изначально curr = 0 для request[i]

• at fromi time curr will be increased by numProcessi
• at toi time curr will be decreased by numProcessi

в любой момент времени, если curr>capacity , просто верните false. Выполните следующие шаги, чтобы решить проблему:

• Инициализировать вектор пары v[].
• Перебрать диапазон [0, request.size()) с помощью переменной i и выполнить следующие задачи:
  • Поместите пару {request[i][1], request[i][0]} в вектор v[].
  • Поместите пару {request[i][2], -request[i][0]} в вектор v[].
• Отсортируйте вектор v[].
• Инициализируйте переменную curr как 0.
• Перебрать диапазон [0, v.size()) с помощью переменной i и выполнить следующие задачи:
  • Добавьте v[i].second к переменной curr.
  • Если curr больше, чем вместимость , верните false.
• После выполнения вышеуказанных шагов верните true в качестве ответа.

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

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