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

3
4 
3 
6 

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

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!