Вопрос: Напишите функцию, которая объединяет пересекающиеся интервалы.
Например, учитывая [(2, 6), (7, 10), (4, 6), (12, 13)], вы должны вернуть [(2, 6), (7, 10), (12, 13) )],
Например, учитывая [(1, 4), (6,9), (3, 5), (7,8)], вы должны вернуть [(1, 5), (6, 9)].
Подсказки:
- Было бы проще сортировать интервалы по времени начала,
- Вы можете использовать стек для хранения объединенных интервалов,
- Вам нужно перебирать интервалы, объединяя их, если дата начала предшествует концу последних интервалов, или нажимать новый.
Решение:
func mergingIntervals(intervals: [(Int, Int)]) -> [(Int, Int)] {
// 1.
guard intervals.count > 1 else { return intervals }
// 2.
let sortedIntervals = intervals.sorted { $0.0 < $1.0 }
// 3.
var result = Array(intervals[0..<1])
// 4.
for interval in sortedIntervals {
// 5.
let top = result.last! // cannot be empty
if interval.0 >= top.1 {
result.append(interval)
} else {
result[result.count - 1] = (top.0, max(top.1, interval.1))
}
}
// 6.
return result
}
Пояснения:
1. Если интервал один и сливать нечего, вернём список.
guard intervals.count > 1 else { return intervals }
2. Отсортируем интервалы по времени начала.
let sortedIntervals = intervals.sorted { $0.0 < $1.0 }
3. Создадим результирующий массив с первым событием.
var result = Array(intervals[0..<1])
4. Теперь перебираем все отсортированные интервалы.
for interval in sortedIntervals {
5. Если текущий интервал начинается после окончания верхнего в результате, добавим его в результирующий массив. В противном случае давайте обновим последний интервал результатов последним временем окончания (максимальное текущее время окончания и время последнего результата).
let top = result.last! // cannot be empty
if interval.0 >= top.1 {
result.append(interval)
} else {
result[result.count - 1] = (top.0, max(top.1, interval.1))
}
6. В конце концов, верните все объединенные интервалы.
return result
Сложность:
- Временная сложность: сортировка всех интервалов приводит к временной сложности O (n log n),
- Пространственная сложность: как и в худшем случае, нет перекрывающихся интервалов, а пространственная сложность линейна O(n).
Тест-кейсы:
public func testMergingIntervals() {
assert(mergingIntervals(intervals: [(2, 6), (7, 10), (4, 6), (12, 13)]).debugDescription == "[(2, 6), (7, 10), (12, 13)]", "mergingIntervals 1 not equal")
assert(mergingIntervals(intervals: [(1, 4), (6,9), (3, 5), (7,8)]).debugDescription == "[(1, 5), (6, 9)]", "mergingIntervals 2 not equal")
}
Следовать за:
Найдите минимальное количество помещений для проведения этих встреч.
Например, учитывая [(30, 75), (0, 50), (60, 150)], вы должны вернуть 2,
Например, учитывая [(1, 3), (5, 7), (2, 4), (6, 8)], вы должны вернуть 2,
Например, учитывая [(1, 3), (7, 9), (4, 6), (10, 13)], вы должны вернуть 1.
Подсказки:
- На этот раз вам нужно разделить время начала и окончания,
- Вам нужно рассчитать максимум в параллельных встречах,
- Добавляйте одну комнату, когда начинается любое собрание, и удаляйте одно помещение, когда любое собрание останавливается.
Решение:
func minRooms(meetings: [(Int, Int)]) -> Int {
// 1.
guard meetings.count > 1 else {
return meetings.count
}
// 2.
var starts = [Int]()
var ends = [Int]()
// 3.
for meeting in meetings {
let (start, end) = meeting
starts.append(start)
ends.append(end)
}
// 4.
starts.sort()
ends.sort()
// 5.
var maxRooms = 0
var currentRooms = 0
var indexStart = 0
var indexEnd = 0
// 6.
while indexStart < starts.count {
if starts[indexStart] < ends[indexEnd] {
// 7.
currentRooms += 1
indexStart += 1
} else {
// 8.
currentRooms -= 1
indexEnd += 1
}
// 9.
maxRooms = max(maxRooms, currentRooms)
}
// 10.
return maxRooms
}
Пояснения:
1. Если собраний меньше двух, нам нужно столько комнат, сколько у нас собраний (0 или 1).
guard meetings.count > 1 else {
return meetings.count
}
2. Создадим отдельные массивы для времени начала и окончания.
var starts = [Int]() var ends = [Int]()
3. Из всех встреч заполним массивы времени начала и окончания.
for meeting in meetings {
let (start, end) = meeting
starts.append(start)
ends.append(end)
}
4. Отсортируем оба временных массива.
starts.sort() ends.sort()
5. Определим некоторые переменные (максимальное количество комнат, текущее количество комнат, индекс времени начала, индекс времени окончания).
var maxRooms = 0 var currentRooms = 0 var indexStart = 0 var indexEnd = 0
6. Давайте повторять до тех пор, пока начальный индекс не будет равен или больше, чем количество начальных моментов.
while indexStart < starts.count {
7. Если текущее время начала меньше текущего времени окончания, увеличим текущее количество комнат и индекс времени начала.
if starts[indexStart] < ends[indexEnd] {
currentRooms += 1
indexStart += 1
8. Если текущее время окончания больше или равно текущему времени начала, уменьшим текущее количество комнат и увеличим индекс времени окончания.
} else {
currentRooms -= 1
indexEnd += 1
}
9. Сохраняйте максимальное количество комнат (предыдущее максимальное и текущее количество комнат).
maxRooms = max(maxRooms, currentRooms)
10. Вернуть максимальное количество необходимых комнат.
return maxRooms
Сложность:
- Сложность времени: сортировка всех времен начала и окончания приводит к сложности времени O (n log n),
- Сложность пространства: разделение времени начала и окончания делает сложность пространства линейной O(n).
Тест-кейсы:
public func testMinRooms() {
assert(minRooms(meetings: [(30, 75), (0, 50), (60, 150)]) == 2, "minRooms 1 not equal")
assert(minRooms(meetings: [(1, 3), (5, 7), (2, 4), (6, 8)]) == 2, "minRooms 2 not equal")
assert(minRooms(meetings: [(1, 3), (7, 9), (4, 6), (10, 13)]) == 1, "minRooms 3 not equal")
}
Следовать за:
Больше никаких уточняющих вопросов.
‹‹ Структуры данных, алгоритмы и вопросы для интервью ››
Повышение уровня кодирования
Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:
- 👏 Хлопайте за историю и подписывайтесь на автора 👉
- 📰 Смотрите больше контента в публикации Level Up Coding
- 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"
🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу
