fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. /**
  8.  * Logic Function: O(N) using Difference Array
  9.  */
  10. int findMaxPeople(int n, const vector<pair<int, int>>& requirements) {
  11.     // Size n + 1 allows index n to be accessed safely
  12.     vector<int> diff(n + 1, 0);
  13.  
  14.     for (int i = 0; i < n; ++i) {
  15.         int start = requirements[i].first + 1;
  16.         int end = requirements[i].second + 1;
  17.  
  18.         if (start <= n) {
  19.             diff[start]++;
  20.             if (end + 1 <= n) {
  21.                 diff[end + 1]--;
  22.             }
  23.         }
  24.     }
  25.  
  26.     int max_people = 0;
  27.     int current_willing = 0;
  28.  
  29.     for (int i = 1; i <= n; ++i) {
  30.         current_willing += diff[i];
  31.         // If 'current_willing' people are okay with group size 'i'
  32.         if (current_willing >= i) {
  33.             max_people = i;
  34.         }
  35.     }
  36.  
  37.     return max_people;
  38. }
  39.  
  40. int main() {
  41.     // Example Input:
  42.     // 6 people
  43.     // 1 2 -> Range [2, 3]
  44.     // 1 4 -> Range [2, 5]
  45.     // 0 3 -> Range [1, 4]
  46.     // 0 1 -> Range [1, 2]
  47.     // 3 4 -> Range [4, 5]
  48.     // 0 2 -> Range [1, 3]
  49.  
  50.     int n = 6;
  51.     vector<pair<int, int>> requirements = {
  52.         {1, 2}, {1, 4}, {0, 3}, {0, 1}, {3, 4}, {0, 2}
  53.     };
  54.  
  55.     int result = findMaxPeople(n, requirements);
  56.  
  57.     cout << "Maximum group size: " << result << endl;
  58.  
  59.     return 0;
  60. }
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum group size: 3
https://ideone.com/xXeKmB
language:
C++ (gcc 8.3)
created:
1 day 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!