В качестве разминочной эта задача очень даже ничего. Для решения её нам необходимо знать всего лишь как быстро отсортировать список отрезков по их началу и применить кое-какие общие рассуждения.
Для удобства сортировки и отсутствия желания писать компаратор можно воспользоваться стандартной структурой pair<int,int> где будет хранится начальная и конечная точки отрезка.
Имея отрезки отсортированными очевидно, что взяв некий i-тый отрезок не один из последующих отрезков не может располагаться левее, в данном случае можно точку начала отрезка можно перенести на последующий отрезок, а в качестве конца выбрать max из координат концов. Логику работы можно проследить на следующем куске кода:
Полный код решения задачи - здесь.
* This source code was highlighted with Source Code Highlighter.
- sort(mas.begin(),mas.end());
- int answer = 0;
- int begin = mas[0].first;
- int end = mas[0].second;
- for(int i=1;i<mas.size();i++)
- {
- if (mas[i].second < end)
- answer ++;
- else
- if (mas[i].first > begin)
- {
- begin = mas[i].first;
- end = mas[i].second;
- }
- else end = mas[i].second;
- }
Комментариев нет:
Отправить комментарий