Сортировки, жадность (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 работ. У каждой работы есть время выполнения ti. К моменту T выполнить максимальное число работ.
    2. Есть n работ. У каждой есть дедлайн di и время выполнения ti. Можно ли успеть выполнить все работы?
    3. Даны n гномов. Если i-го гнома укладывать спать ai минут, он потом спит bi минут. Можно ли сделать так, чтобы все гномы уснули? (принцип доказательства: выбор максимума)
    4. Есть n спортсменов. i-й спортсмен имеет вес mi и может держать на своих плечах суммарную массу si. Можно ли построить башню из всех спортсменов?
    5. Есть работы. У каждой работы есть ti − время выполнения и fi − штраф. Нужно минимизировать ∑ Tifi, где Ti − момент выполнения работы.
    6. Автоматическое придумываение компаратора: попытаться сделать swap
    7. Максимальное скалярное произведение (даны два вектора, координаты одного из них можно переставлять)
    8. Задача о двух станках (без доказательства, просто применяем метод)
    9. [skipped] Есть n работ. У каждой есть дедлайн di и время выполнения ti. Успеть выполнить максимальное число работ.