Найдите минимальное и максимальное число людей, входящих или выходящих из комнаты

Опубликовано: 19 Сентября, 2022

Дана двоичная строка person , где «1» и «0» представляют людей, входящих и выходящих из комнаты соответственно. Задача состоит в том, чтобы найти минимальное и максимальное количество различных лиц, входящих или выходящих из здания.

Примеры:

Input: “000”
Output: Minimum Persons: 3
Maximum Persons: 3
Explanation: 3 distinct persons left the building.

Input: “111”
Output: Minimum Persons: 3
Maximum Persons: 3
Explanation: 3 distinct persons entered the building.

Input: “110011”
Output: Minimum Persons: 2
Maximum Persons: 6
Explanation: 2 persons entered->those 2 persons left->same 2 persons entered 
to account for minimum 2 persons.
All persons entered or left are distinct to account for maximum 6 persons.

Input: “10101”
Output: Minimum Persons: 1
Maximum Persons: 5
Explanation:  1 person entered- > he left -> again entered -> again left -> and again entered 
to account for minimum 1 person.
All persons entered or left are distinct to account for maximum 5 persons.

Подход : Задача может быть решена на основе следующего наблюдения:

  • Each person entering or leaving the room can be a unique person. This will give the maximum number of persons that can enter a room. This will be equal to the total number of times a leaving or entering operation is performed,
  • Each time the same persons who are leaving the room are entering the room next time. So the maximum among the people leaving at a time or entering at a time is the minimum possible number of unique persons.

Следуйте приведенной ниже иллюстрации для лучшего понимания.

Иллюстрация:

Consider persons = “10101”

For finding the maximum:

        => At first, first person (say P1) enters the room
        => Then, second person (say P2) exits the room
        => Then, third person (say P3) enters the room
        => Then, fourth person (say P4) exits the room
        => At last, fifth person (say P5) enters the room

Total 5 persons enter or leave the room at most.

For finding the minimum possible persons:

        => At first, first person (say P1) enters the room.
        => Then P1 exits the room.
        => Then P1 again enters the room.
        => Then again P1 exits the room.
        => At last P1 again enters the room.

So at least one person enters or leaves the room.

Выполните следующие шаги, чтобы реализовать вышеуказанное наблюдение:

  • Начните обход всей строки лиц .
  • Если person[i] = '1', то вводится приращение, иначе вводится уменьшение.
  • Сохраните максимальное значение введенного и N (размер строки лиц) в качестве первого и второго значения пары result .
  • В этом цикле, если в любой момент введенное значение становится отрицательным, повторно инициализируйте его значением 0 и увеличьте первое значение результата пары.
  • Возвращает результат как последнюю пару, содержащую минимальное и максимальное количество различных людей в качестве первого и второго значения соответственно.

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

Временная сложность: O(N), где N — длина строки person .
Вспомогательное пространство: О(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ