Условие задачи

Даны заявки на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия ($si$ и $fi$ для $i$-ой заявки). Нужно оставить максимальное количество заявок так, чтобы они не перекрывали друг друга по времени. При этом если одна заявка закончилась во время $t$, а следующая началась во время $t$, то их можно ставить подряд.

---

Решение

Найдем заявку с самым минимальным временем окончания. Нам всегда выгодно включить её в наш ответ, потому что она заканчивается раньше остальных заявок. Поэтому, если в ответе первой будет какая-то другая заявка, мы можем заменить её на минимальную по времени окончания. При этом новых пересечений не появится, так как время конца заявки стало ещё меньше.

После выбора заявки с самым минимальным временем конца, уберем из рассмотрения все заявки, которые с ней пересекаются. Продолжаем выбирать заявку по минимальному времени конца и убирать из рассмотрения пересекающиеся с ней заявки, пока они не закончатся.

---

Сложность

Сложность алгоритма - $O(n*log_2 n)$, где $n$ - количество заявок.

---

Псевдокод

Функция_вычисления(список заявок)
    сортируем список заявок по времени окончания
    нужные заявки <- пустой список
    последняя заявка <- (0, 0)
    
    для i в списке заявок
        если время окончания последней заявки <= времени начала заявки i
            то в нужные заявки добавлем i
            последняя заявка <- i
            
    вернуть длину списка нужных заявок

---

Реализация на Python

Аннотация:
count_applications - функция для вычисления максимального количества непересекающихся заявок
applications - список заявок, каждая заявка представлена кортежем из двух элементов: время начала и время окончания
ans - список выбранных заявок
last_application - переменная для отслеживания последней добавленной заявки

def count_applications(applications):  
    applications = sorted(applications, key=lambda x: x[1])  
    ans = list()  
    last_application = (0, 0)  
    
    for i in applications:  
        if last_application[1] <= i[0]:  
            ans.append(i)  
            last_application = i  
            
    return len(ans)

---

Олимпиадная реализация на C++

Аннотация:
comp - функция для сравнения заявок по времени окончания, возвращающая `true`, если время окончания первой заявки меньше времени окончания второй заявки
appl_1 - первая заявка (пара значений: время начала и время окончания)
appl_2 - вторая заявка (пара значений: время начала и время окончания)
k_appl - функция для вычисления максимального количества непересекающихся заявок
appl - вектор заявок, каждая заявка представлена парой значений: время начала и время окончания
ans - вектор для хранения выбранных заявок
l_appl - переменная для отслеживания последней добавленной заявки

typedef pair<int, int> ii;

bool comp(ii appl_1, ii appl_2) {
    return appl_1.second < appl_2.second;    
}

int k_appl(vector<ii>  appl){
    sort(appl.begin(), appl.end(), comp);
    vector<ii> ans;
    ii l_appl = make_pair(0, 0);
    
    for (ii appl : appl) {
        if (l_appl.second <= appl.first){
            answer.push_back(appl);
            l_appl = application;
        }
    }
    
    return ans.size();
} 

---

Продуктовая реализация на C++

Аннотация:
compare - функция для сравнения заявок по времени окончания, возвращающая `true`, если время окончания первой заявки меньше времени окончания второй заявки
first_application - первая заявка (пара значений: время начала и время окончания)
second_application - вторая заявка (пара значений: время начала и время окончания)
count_applications - функция для вычисления максимального количества непересекающихся заявок
applications - вектор заявок, каждая заявка представлена парой значений: время начала и время окончания
amount_application - вектор для хранения выбранных заявок
last_application - переменная для отслеживания последней добавленной заявки

bool compare(pair<int, int> first_application, 
             pair<int, int> second_application) {
    return first_application.second < second_application.second;    
}

int count_applications(vector<pair<int, int>>  applications){
    sort(applications.begin(), applications.end(), compare);
    vector<pair<int, int>> amount_application;
    pair<int, int> last_application = make_pair(0, 0);
    
    for (pair<int, int> application : applications) {
        if (last_application.second <= application.first){
            amount_application.push_back(application);
            last_application = application;
        }
    }
    
    return amount_application.size();
}