В этом материале мы разберём задачу, которая может попасться вам на собеседовании. В этом разборе мы покажем неочевидный способ применения сортировки.
Иногда в задачах алгоритмы сортировки используются весьма необычным способом. Один из таких приёмов — сортировка событий. В следующем видео мы рассмотрим, как этот приём используется для решения задачи с LeetCode [Minimum Number of Arrows to Burst Balloons]. Внимательно изучите условие этой задачи, чтобы лучше понять материал видео.
Иногда в задачах алгоритмы сортировки используются весьма необычным способом. Один из таких приёмов — сортировка событий. В следующем видео мы рассмотрим, как этот приём используется для решения задачи с LeetCode [Minimum Number of Arrows to Burst Balloons]. Внимательно изучите условие этой задачи, чтобы лучше понять материал видео.
Решение задачи с LeetCode, рассмотренное в предыдущем видео.
class Solution {
public:
enum Type {
Start,
Finish,
};
struct Event {
int x;
Type type;
size_t index;
bool operator<(const Event& rhs) const {
return tie(x, type, index) < tie(rhs.x, rhs.type, rhs.index);
}
};
int findMinArrowShots(vector<vector<int>>& points) {
vector <Event> events;
for (size_t i = 0; i < points.size(); ++i) {
events.push_back(Event{points[i][0], Start, i});
events.push_back(Event{points[i][1], Finish, i});
}
sort(events.begin(), events.end());
int result = 0;
vector <bool> is_alive(points.size(), true);
vector <size_t> current_open;
for (Event e : events) {
if (e.type == Start) {
current_open.push_back(e.index);
} else if (is_alive[e.index]) {
++result;
for (auto i : current_open) {
is_alive[i] = false;
}
current_open.clear();
}
}
return result;
}
};
