Сложность: hard
Вам дан двумерный целочисленный массив 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⃣Пройдите по каждому интервалу, добавляя необходимые числа в множество так, чтобы каждый интервал содержал не менее двух чисел из этого множества.
😎 Решение:
func minSetSize(_ intervals: [[Int]]) -> Int {
let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
var nums = [Int]()
for interval in sortedIntervals {
let start = interval[0]
let end = interval[1]
if nums.isEmpty || nums.last! < start {
nums.append(end - 1)
nums.append(end)
} else if nums.last! == end - 1 {
nums.append(end)
}
}
return nums.count
}Ставь 👍 и забирай 📚 Базу знаний