Жадные алгоритмы

Что такое жадные алгоритмы?
Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

Задача об отрезках
Даны N отрезков на прямой, т.е. каждый отрезок задаётся парой координат (X1, X2). Рассмотрим объединение этих отрезков и найдём его длину.
X11
X12
X21
X22
X31
X32

Решение
Положим все координаты концов отрезков в массив X и отсортируем его по значению координаты. Дополнительное условие при сортировке - при равенстве координат первыми должны идти левые концы. Кроме того, для каждого элемента массива будем хранить, относится он к левому или к правому концу отрезка. Теперь пройдёмся по всему массиву, имея счётчик C перекрывающихся отрезков. Если C отлично от нуля, то к результату добавляем разницу Xi - Xi-1. Если текущий элемент относится к левому концу, то увеличиваем счётчик C, иначе уменьшаем его.

Реализация

Задача
Дан массив из N положительных чисел, надо найти в нем несколько чисел, идущих подряд, так, чтобы их сумма была больше K, а чисел в нем содержалось бы как можно меньше.

Решение
Зафиксируем позицию первого из искомых чисел (левый указатель). Найдем минимальную позицию второго числа (правого указателя), где сумма чисел между ними будет больше K (основное условие). Запомним количество чисел в найденном отрезке – это наш текущий результат. Будем сдвигать левый указатель, пока основное условие не перестанет выполняться, на каждом шаге пытаемся улучшить результат. Снова фиксируем левый указатель и продолжаем выполнение алгоритма, пока сдвиги указателей возможны.