Секретарь
общеобразовательного учреждения Марта Георгиевна ежедневно начинала свой
рабочий день с претензий к директору:
- Вот Вы, Иван Иванович,
заместителю по учебной части программу для составления расписания уже
приобрели. А что мне делать? Ведь мне нужно согласно Ваших требований составить
график приема посетителей, а программу для планирования работы администрации Вы
мне не приобрели...
Попробуйте помочь секретарю
в ее роботе. Для этого вам нужно организовать прием посетителей на основании
пожеланий, сделанных ими в соответствующей книге у секретаря.
Прием двух посетителей
одновременно запрещен. В момент завершения приема одного посетителя может
начаться прием другого – они встретились в дверях кабинета.
Вход.
В первой строке находится количество посетителей n (n ≤ 1000), записавшихся на
прием. В последующих n строках расположено по
два числа T1i – время начала встречи с директором
и через пробел T2i – время ее завершения в формате hh:mm. Известно, что время
задано в течении одних суток, все T2i ≥ T1i.
Выход.
Выведите максимальное количество посетителей, которое сможет
принять директор учреждения на протяжении рабочего дня.
|
Пример входа |
Пример выхода |
|
4 09:10 13:05 14:25 14:30 14:20 15:15 15:00 17:00 |
3 |
РЕШЕНИЕ
жадные алгоритмы
Анализ алгоритма
Создадим массив
отрезков – временных интервалов [T1i; T2i). Отсортируем их
по возрастанию времени окончания.
Далее жадным
образом выбираем посетителей: перебираем интервалы слева направо и выбираем те,
которые не пересекаются с уже выбранными.
Реализация алгоритма
Объявим класс
отрезок, который будет хранить временной интервал [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 %d:%d",
&h1, &m1, &h2, &m2);
Время в интервалах сохраняем в минутах.
v.push_back(segment(h1 * 60 +
m1, h2 * 60 + m2));
}
Сортируем отрезки времени.
sort(v.begin(),
v.end(), f);
Принимаем посетителя, которому соответствует нулевой
интервал (интервалы нумеруем с нуля). Пусть текущему посетителю, которого
принимает директор, соответствует интервал времени cur. Поскольку
директор всегда примет нулевого посетителя, установим cur = 0. В
переменной res подсчитываем количество принятых
посетителей. Поскольку
директор принимает посетителя номер 0, то сначала установим res = 1.
cur =
0; res = 1;
Перебираем интервалы, начиная с i = 1.
for (i = 1; i < v.size(); i++)
{
Ищем интервал, начало которого не меньше времени окончания
текущего. Принимаем посетителя из этого интервала и устанавливаем этот интервал
текущим.
if (v[i].start >= v[cur].fin)
{
cur = i;
res++;
}
}
Выводим количество принятых посетителей.
printf("%d\n", res);
Реализация алгоритма – вектор пар
Массив отрезков
храним в векторе v.
vector<pair<int, int> > v;
Читаем входные данные. Время преобразуем в минуты. Время
окончания ставим в паре первым, так как по умолчаннию вектор пар сортируется по
первой компоненте.
scanf("%d", &n);
while (n--)
{
scanf("%d:%d %d:%d", &h1, &m1,
&h2, &m2);
v.push_back(make_pair(h2
* 60 + m2, h1 * 60 + m1));
}
Сортируем пары.
sort(v.begin(), v.end());
В переменной res подсчитываем количество выбранных
отрезков.
i = res = 0;
while (i <
v.size())
{
В переменную temp заносим конец
очередного выбранного отрезка.
res++; temp =
v[i++].first; // end
Ищем следующий отрезок, который начинается не раньше temp.
while (i < v.size() && v[i].second < temp) i++;
}
Выводим количество принятых посетителей.
printf("%d\n", res);
Java реализация
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++)
{
String s = con.next();
StringTokenizer st = new StringTokenizer(s, ":");
int h = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int start = h * 60 + m;
s = con.next();
st = new StringTokenizer(s, ":");
h = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
int fin = h * 60 + m;
seg.add(new Segment(start,fin));
}
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();
}
}