fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. struct Spotkanie
  9. {
  10.     int start, end; //czasy przechowujemy w minutach
  11.     int id;
  12. };
  13.  
  14. int main()
  15. {
  16.     ios_base::sync_with_stdio(false);
  17. 	//cin.tie(nullptr);
  18.  
  19.     int t;
  20.     cin >> t;
  21.     while (t--)
  22.     {
  23.         int ile_sal, ile_spotkan;
  24.         cin >> ile_sal >> ile_spotkan;
  25.         list<Spotkanie> spotkania;
  26.  
  27.         for (int i = 0; i < ile_spotkan; ++i)
  28.         {
  29.             int rg, rm, zg, zm;
  30.             char dummy;
  31.  
  32.             cin >> rg >> dummy >> rm >> zg >> dummy >> zm;
  33.  
  34.             spotkania.push_back(Spotkanie{rg * 60 + rm, zg * 60 + zm, i + 1});
  35.         }
  36.  
  37.         spotkania.sort([](const Spotkanie& a, const Spotkanie& b)->bool
  38.         {
  39.             if (a.start != b.start)
  40.             {
  41.                 return a.start < b.start;
  42.             }
  43.             return a.end > b.end;
  44.         });
  45.  
  46.         vector<vector<int>> sale(ile_spotkan); //bedzie przechowywac poszczegolne sale, a one poszczegolne spotkania, ktore sie w nich odbeda
  47.         int odbedzie_sie = 0;
  48.  
  49.         for (int i = 0; i < ile_spotkan; ++i) //zachlannie pakujemy spotkania do kazdej sali po kolei
  50.         {
  51.             int koniec_obecnego = -1;
  52.             if (spotkania.empty()) //jesli nie wykorzystamy wszystkich sal
  53.             {
  54.                 break;
  55.             }
  56.  
  57.             for (auto spotkanie = spotkania.begin(); spotkanie != spotkania.end();)
  58.             {
  59.                 if (spotkanie->start >= koniec_obecnego) //jesli mozna wsadzic do obecnej sali jeszcze jedno spotkanie
  60.                 {
  61.                     koniec_obecnego = spotkanie->end;
  62.                     sale[i].push_back(spotkanie->id);
  63.                     spotkanie = spotkania.erase(spotkanie);
  64.                 }
  65.                 else
  66.                 {
  67.                     ++spotkanie;
  68.                 }
  69.             }
  70.         }
  71.  
  72.         sort(sale.begin(), sale.end(), [](const auto& a, const auto& b)->bool {return a.size() > b.size();});
  73.         for (int i = 0; i < min(ile_sal, ile_spotkan); ++i)
  74.         {
  75.             odbedzie_sie += sale[i].size();
  76.         }
  77.  
  78.         cout << odbedzie_sie << '\n';
  79.         for (int i = 0; i < min(ile_sal, ile_spotkan); ++i)
  80.         {
  81.             if (sale[i].empty())
  82.             {
  83.                 break;
  84.             }
  85.  
  86.             for (int j: sale[i])
  87.             {
  88.                 cout << j << ' ';
  89.             }
  90.  
  91.             cout << '\n';
  92.         }
  93.         cout << '\n';
  94.     }
  95. }
  96.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2
1 3
00:00 02:00
00:01 00:02
00:02 00:03
2 6
01:00 03:00
03:00 09:00
01:00 05:00
05:00 07:00
07:00 10:00
09:00 10:00
stdout
copy 
2
2 3 

6
3 4 5 
1 2 6
https://ideone.com/QGhxFP
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!