#hard
Задача: 749. Contain Virus

Вирус быстро распространяется, и ваша задача - поместить зараженную область в карантин, установив стены. Мир моделируется как бинарная сетка m x n isInfected, где isInfected[i][j] == 0 обозначает незараженные клетки, а isInfected[i][j] == 1 - клетки, зараженные вирусом. Между любыми двумя соседними клетками, расположенными в четырех направлениях, может быть установлена стена (и только одна стена) на общей границе. Каждую ночь вирус распространяется на все соседние клетки во всех четырех направлениях, если не блокируется стеной. Ресурсы ограничены. Каждый день вы можете устанавливать стены только вокруг одного региона (то есть пораженной области (непрерывного блока зараженных клеток), которая угрожает наибольшим количеством незараженных клеток на следующую ночь). Ничьей не будет никогда. Верните количество стен, использованных для карантина всех зараженных регионов. Если мир будет полностью заражен, верните количество использованных стен.

Пример:

Input: isInfected = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]
Output: 10

👨‍💻 Алгоритм:

1⃣Определите все зараженные регионы и для каждого региона определите количество угрожаемых незараженных клеток.

2⃣Выберите регион, который угрожает наибольшему количеству незараженных клеток, и установите вокруг него стены. Распространите вирус на все соседние клетки для всех остальных регионов.

3⃣Повторяйте шаги 1-2, пока все регионы не будут окружены стенами или мир не будет полностью заражен. Подсчитайте и верните количество использованных стен.

😎 Решение:

def containVirus(isInfected):
    def neighbors(r, c):
        for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
            if 0 <= nr < len(isInfected) and 0 <= nc < len(isInfected[0]):
                yield nr, nc
    
    def dfs(r, c, region, frontiers, walls):
        stack = [(r, c)]
        region.add((r, c))
        while stack:
            r, c = stack.pop()
            for nr, nc in neighbors(r, c):
                if isInfected[nr][nc] == 1 and (nr, nc) not in region:
                    stack.append((nr, nc))
                    region.add((nr, nc))
                elif isInfected[nr][nc] == 0:
                    frontiers.add((nr, nc))
                    walls.add((r, c, nr, nc))
    
    total_walls = 0
    while True:
        regions = []
        frontiers = []
        walls = []
        visited = set()
        
        for r in range(len(isInfected)):
            for c in range(len(isInfected[0])):
                if isInfected[r][c] == 1 and (r, c) not in visited:
                    region = set()
                    frontier = set()
                    wall = set()
                    dfs(r, c, region, frontier, wall)
                    visited |= region
                    if frontier:
                        regions.append(region)
                        frontiers.append(frontier)
                        walls.append(wall)
        
        if not regions:
            break
        
        max_threat_index = max(range(len(frontiers)), key=lambda i: len(frontiers[i]))
        total_walls += len(walls[max_threat_index])
        
        for i, region in enumerate(regions):
            if i == max_threat_index:
                for r, c in region:
                    isInfected[r][c] = -1
            else:
                for r, c in frontiers[i]:
                    isInfected[r][c] = 1
    
    return total_walls

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

👨‍💻 Алгоритм:

1⃣Отсортируйте интервалы по их конечным точкам.

2⃣Инициализируйте пустое множество для хранения чисел.

3⃣Пройдите по каждому интервалу, добавляя необходимые числа в множество так, чтобы каждый интервал содержал не менее двух чисел из этого множества.

😎 Решение:

def minSetSize(intervals):
    intervals.sort(key=lambda x: x[1])
    nums = []
    for start, end in intervals:
        if not nums or nums[-1] < start:
            nums.append(end - 1)
            nums.append(end)
        elif nums[-1] == end - 1:
            nums.append(end)
    return len(nums)

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 759. Employee Free Time

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

👨‍💻 Алгоритм:

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

from typing import List

class Interval:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end

def employeeFreeTime(schedule: List[List[Interval]]) -> List[Interval]:
    intervals = []
    for employee in schedule:
        intervals.extend(employee)
    
    intervals.sort(key=lambda x: x.start)
    
    merged = []
    for interval in intervals:
        if not merged or merged[-1].end < interval.start:
            merged.append(interval)
        else:
            merged[-1].end = max(merged[-1].end, interval.end)
    
    free_time = []
    for i in range(1, len(merged)):
        if merged[i].start > merged[i-1].end:
            free_time.append(Interval(merged[i-1].end, merged[i].start))
    
    return free_time

Ставь 👍 и забирай 📚 Базу знаний