Сортировки, жадность (16 сентября 2016)

1. [10 минут] Применяем сортировку на C++, Java, переопределяем компаратор
1. C++: [code] [code] [code] [code]
2. java: =(


2. [40 минут] Про отрезки на прямой и события
1. Максимальное число непересекающихся отрезков
2. Найти длину объединения отрезков
3. Найти точку, покрытую максимальным числом отрезков
4. Найти количество пар пересекающихся отрезков
5. [skipped] Для каждого отрезка найти количество пересекающихся с ним
6. Даны n отрезков на прямой. Для каждого k от 0 до n посчитать длину части прямой, покрытой ровно k отрезками.


3. [40 минут] Задачи на сортировку, жадности, придумывание компаратора
1. Есть n работ. У каждой работы есть время выполнения t_i. К моменту T выполнить максимальное число работ.
2. Есть n работ. У каждой есть дедлайн d_i и время выполнения t_i. Можно ли успеть выполнить все работы?
3. Даны n гномов. Если i-го гнома укладывать спать a_i минут, он потом спит b_i минут. Можно ли сделать так, чтобы все гномы уснули? (принцип доказательства: выбор максимума)
4. Есть n спортсменов. i-й спортсмен имеет вес m_i и может держать на своих плечах суммарную массу s_i. Можно ли построить башню из всех спортсменов?
5. Есть работы. У каждой работы есть t_i − время выполнения и f_i − штраф. Нужно минимизировать ∑ T_if_i, где T_i − момент выполнения работы.
6. Автоматическое придумываение компаратора: попытаться сделать swap
7. Максимальное скалярное произведение (даны два вектора, координаты одного из них можно переставлять)
8. Задача о двух станках (без доказательства, просто применяем метод)
9. [skipped] Есть n работ. У каждой есть дедлайн d_i и время выполнения t_i. Успеть выполнить максимальное число работ.