3 задачи 1 курса на с#

1) Дано K упорядоченных списков чисел. Нужно вернуть первые N элементов из их объединения.
Предложите алгоритм эффективнее тривиального, то есть быстрее, чем за O(NK)
2) Версионный стек. Поддерживаются операции Push, Pop, Rollback. Состояния стека после
выполнения этих операций нумеруются. С помощью Rollback можно откатиться на любое
состояние, указав его номер. Rollback тоже можно откатить. Помимо этого, существует операция
Forget, позволяющая забыть всю историю изменений. После Forget нумерация операций
начинается с начала, Forget нельзя откатить. Все 4 операции должны работать за O(1).
3) Пересечение отрезков. Дано N отрезков, каждый из которых параллелен либо оси X, либо оси Y.
Необходимо найти любые два пересекающихся отрезка, либо сказать, что таких нет. Сложность —
быстрее, чем за O(N^2)