Delphi(1й курс) Жадный алгоритм

[Archetype]

Здравствуйте гении!
Прошу помочь разобраться с задачкой, а именно объяснить
1)что такое жадный алгоритм, и как его применить в этой задаче?
2)что такое сортировка вставками?
3)Алгоритм выполнения этой задачи(я путаюсь)
Я не прошу Вас за меня писать код, прошу просто объяснений, а программу я сам напишу если пойму

[Z1000000]

Википедия:
Жадный алгоритм
сортировка вставками.

Смотрел?

[Archetype]

посмотрел про вставки, понял а про жадный не понял...

[Archetype]

Объяснит мне кто?

[sabbathist]

Жадный алгоритм выбирает на каждом этапе оптимальное (для этого этапа) решение. Обычно ему предшествует сортировка. Сейчас я попытаюсь показать пример его использования на классической задаче на жадный алгоритм (по-моему, называется "задача о встречах" или около того):

Условие:
У начальника есть список, состоящий из n (1<=n<=1000) встреч. Каждая встреча характеризуется двумя параметрами: временем начала и временем окончания. Время встреч может пересекаться. Начальнику необходимо выбрать максимальное непересекающееся множество встреч.

(условие писал по памяти)

Решение:
сортируем все встречи по концу(т.е. чем раньше встреча заканчивается, тем раньше она у нас будет стоять в массиве).
А теперь сам жадник: идем по массиву, и смотрим: если текущая встреча начинается позже чем заканчивается последняя из уже выбранных, то мы ее добавляем в множество выбранных, если начинается раньше (т.е. пересекается) то не добавляем. И так до конца.

Т.е. суть жадника тут в том, чтобы брать первую встречу, которую возможно взять. Док-во корректности, думаю, смысла нет приводить, т.к. тебе оно все равно не пригодится .
Подробнее можно почитать в книге "Алгоритмы: построение и анализ"
Авторы: Кормен, Лейзерсон, Ривест, Штайн.
Вообще, в этой книге можно прочитать обо всем, что касается алгоритмизации (на уровне универа)



UPD: вот блин, я сначала написал пост, а потом заметил твою задачу. Короче, сложность будет зависеть от сложности сортировки. Если сортировка вставками, то O(n^2+n)=O(n^2)

[Archetype]

Спасибо, дошло Пойду строчить, а то зачет скоро

[Archetype]

А вот в задаче написано "Специальная процедура должна преобразовывать любой заданный момент времени, в кол-во секунд с начала суток" Это чот ж за чудо процедура? Как заставить делфи понимать что в 14:02:39 50559 секунд? То есть как сделать, чтобы он определял что первое число надо на 3600 умножить+второе на 60+3е число? %)

[Archetype]

ответьте((

[Z1000000]

Если время храниться в формате TDateTime, то
SecondOfTheDay функция модуля DateUtils Возвращает количество секунд между значением указаным в TDateTime и 12:00:00 AM того же самого дня.

Если нет. То сначала, привести к формату TDateTime функцией EncodeTime;