fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Interval {
  8.     int start, end;
  9.  
  10.     bool operator < (const Interval &i) const {
  11.         return start < i.start || (start == i.start && end < i.end);
  12.     }
  13. };
  14.  
  15. int main() {
  16.     int K;
  17.     cin >> K;
  18.  
  19.     vector<Interval> group;
  20.     int x, y;
  21.     while (cin >> x >> y) {
  22.         group.push_back({ x, y });
  23.     }
  24.  
  25.     std::sort(group.begin(), group.end());                 // O(N lg N)
  26.  
  27.     int i = 0,
  28.         v = group[i].start,
  29.         k = K--;
  30.  
  31.     while (K) {                                            // O(K)
  32.         if (v >= group[i].start && v < group[i].end) {
  33.             v++;
  34.             K--;
  35.         }
  36.         else if (v < group[++i].start) {
  37.             v = group[i].start;
  38.             K--;
  39.         }
  40.     }
  41.  
  42.     std::cout << k << "'th min from these set of intervals is: " << v;
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5
2 4
3 7
stdout
copy 
5'th min from these set of intervals is: 6
https://ideone.com/DMwlgB
language:
C++ (gcc 8.3)
created:
8 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!