Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <utility>
- #include <algorithm>
- #include <vector>
- о
- //так понимаю структура пары чтобы засунуть её в вектор (было дано)
- typedef std::pair <int, int> Segment;
- //функция для сортировки по второму элементу
- bool sortbysec(const std::pair <int, int> &a, const std::pair <int, int> &b){
- return a.second < b.second;
- }
- std::vector <int> get_covering_set(std::vector <Segment> segments) {
- std::vector <int> result;
- // fix this function
- // первый элемент добавляется всегда потому что является надежным шагом
- int a = segments[0].second;
- result.push_back(a);
- // смотрим если левый конец правого отрезка не превышает значения последнего добавленного то переходим к следующему
- for (std::size_t i = 1; i < segments.size(); i++) {
- if(segments[i].first > a){
- a = segments[i].second;
- result.push_back(a);
- }
- }
- return result;
- }
- int main(void) {
- int segments_count;
- std::cin >> segments_count;
- std::vector <Segment> segments(segments_count);
- for (int i = 0; i < segments_count; i++) {
- std::cin >> segments[i].first >> segments[i].second;
- }
- //сортировка по правому концу
- std::sort(segments.begin(), segments.end(), sortbysec);
- //просто проверял как отсортировался вектор
- /*for(int i = 0; i < segments_count; i++){
- std::cout << segments[i].first << " " << segments[i].second << std::endl;
- }*/
- // вывод решения
- std::vector <int> points = get_covering_set(segments);
- std::cout << points.size() << std::endl;
- for (std::size_t i = 0; i < points.size(); i++) {
- std::cout << points[i] << " ";
- }
- std::cout << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement