Ja opisałem wcześniej wersję która spogląda w lewą strone miotły (czyli przeszłość) i tak jak @nalik słusznie zauważył, trzeba sortować po dwóch rzeczach.
Ale wersja @krystian99 ze spoglądaniem w prawą stronę miotły (przyszłość) wydaje mi się prostsza w implementacji i bardziej elegancka i taką popełniłem:
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct Prawnik
{
int a;
int b;
int n;
};
bool sortujePoPocztku(const Prawnik& i, const Prawnik& j) { return i.a < j.a; }
bool sortujePoNumerrze(const Prawnik& i, const Prawnik& j) { return i.n < j.n; }
struct PorownajPrawnikowNaKolejce
{
bool operator ()(const Prawnik& p1, const Prawnik& p2)
{
return p1.b > p2.b;
}
};
int main()
{
int n, k;
scanf("%d%d", &n, &k);
vector<Prawnik> p(n);
for (int i = 0; i < n; ++i)
{
scanf("%d%d", &p[i].a, &p[i].b);
p[i].n = i + 1;
}
// sortujemy po poczatku spotkania
sort(p.begin(), p.end(), sortujePoPocztku);
// znajdujemy maksymalna dlugosc spotkania i moment t w ktorym się ono zaczęło
priority_queue <Prawnik, vector<Prawnik>, PorownajPrawnikowNaKolejce> pq;
int max_spotkanie = 0;
int start_spotkania = -1;
for (int i = 0; i < n; ++i)
{
// zdejmujemy tych ktorych czas juz przeminal (czyli prawnikow ktorzy sobie poszli przed przyjsciem obecnego prawnika)
while ((!pq.empty()) && (pq.top().b <= p[i].a))
{
pq.pop();
}
// dodajemy obecnego prawnika do kolejki
pq.push(p[i]);
// zdejmujemy jak mamy ich juz za duzo (zdejmujemy tych ktorzy najwczesniej sobie pojda)
while (pq.size() > k)
{
pq.pop();
}
// sprawdzamy czy mamy k prawnikow jednoczesnie
if (pq.size() == k)
{
int obecne_spotkania = pq.top().b - p[i].a;
// sprawdzamy czy mamy lepsze rozwiazanie od poprzedniego
if (obecne_spotkania > max_spotkanie)
{
max_spotkanie = obecne_spotkania;
start_spotkania = p[i].a;
}
}
}
printf("%d\n", max_spotkanie);
// wypisujemy prawnikow bioracych udzial w spotkaniu
int koniec_spotkania = start_spotkania + max_spotkanie;
vector<Prawnik> rozwiazanie;
for (int i = 0; i < n; ++i)
{
if ((p[i].a <= start_spotkania) && (p[i].b >= koniec_spotkania))
{
rozwiazanie.push_back(p[i]);
if (rozwiazanie.size() == k)
{
break;
}
}
}
// sortujemy rowiazanie co by sie nam latwiej testy sprawdzalo
sort(rozwiazanie.begin(), rozwiazanie.end(), sortujePoNumerrze);
for (int i = 0; i < k; ++i)
{
printf("%d ", rozwiazanie[i].n);
}
return 0;
}
tutaj są dostępne oficjalne testy:
https://sio2.mimuw.edu.pl/c/oi25-1/tests/119/
mój kod działa dobrze dla wszystkich od pra1a do pra4g, dalej mi się sprawdzać nie chciało.
No to teraz czekamy na liniową wersję (pomijając sortowanie) od @MarekR22 :)