Даны отрезки на
прямой. Какое максимальное количество отрезков можно выбрать так, чтобы никакие
два из них не пересекались? Отрезки считаются открытыми.
Вход. В первой строке
задано количество отрезков n (1
≤ n ≤ 105). В
следующих n строках описаны отрезки: i-ая строка содержит два целых числа li и ri – координаты начала и конца отрезка (1 ≤ li < ri ≤ 109).
Выход. Выведите
максимальное количество непересекающихся отрезков.
Пример
входа 1 |
Пример
выхода 1 |
5 1 4 3 8 7 8 2 5 4 6 |
3 |
|
|
Пример
входа 2 |
Пример
выхода 2 |
4 1 3 2 6 1 8 2 5 |
1 |
жадность
– выбор заявок
Отсортируем
отрезки по правому концу. Выбираем первый отрезок и удаляем все отрезки,
которые с ним пересекаются. Далее выбираем следующий самый левый отрезок и
удаляем те, которые с ним пересекаются. Таким жадным алгоритмом выберем
максимальное количество непересекающихся отрезков.
Объявим класс
отрезок, который будет хранить интервал [start; fin).
class segment
{
public:
int start, fin;
segment(int start, int fin) : start(start), fin(fin) {}
};
Набор входных
интервалов храним в векторе v.
vector<segment> v;
Функция f является компаратором для сортировки интервалов.
Интервалы сортируем по возрастанию их правых концов.
int f(segment a, segment b)
{
return a.fin <= b.fin;
}
Основная часть программы. Читаем входные данные.
scanf("%d", &n);
while (n--)
{
scanf("%d %d", &a,
&b);
v.push_back(segment(a, b));
}
Сортируем отрезки.
sort(v.begin(),
v.end(), f);
Пусть текущим обрабатываемым интервалом будет cur. Алгоритм начинаем с нулевого интервала: cur = 0. В переменной res подсчитываем
количество выбранных интервалов. Поскольку
нулевой интервал изначально выбран, то установим res =
1.
cur = 0; res = 1;
Перебираем интервалы, начиная с i = 1.
for (i = 1; i < v.size(); i++)
{
Ищем интервал, начало которого не меньше конца текущего cur. Как только такой
интервал будет найден, выбираем его и устанавливаем текущим.
if (v[i].start >= v[cur].fin)
{
cur = i;
res++;
}
}
Выводим максимальное количество непересекающихся интервалов.
printf("%d\n", res);
import java.util.*;
class Segment
{
int start, fin;
public
Segment(int start, int fin)
{
this.start = start;
this.fin = fin;
}
}
public class Main
{
public static class
MyFun implements Comparator<Segment>
{
public int
compare(Segment a, Segment b)
{
return a.fin - b.fin;
}
}
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
ArrayList<Segment>
seg = new
ArrayList<Segment>();
for (int i = 0;
i < n; i++)
{
int a = con.nextInt();
int b = con.nextInt();
seg.add(new
Segment(a,b));
}
Collections.sort(seg, new
MyFun());
int cur = 0,
res = 1;
for (int i = 1;
i < seg.size(); i++)
{
if (seg.get(i).start
>= seg.get(cur).fin)
{
cur = i;
res++;
}
}
System.out.println(res);
con.close();
}
}