0
$\begingroup$

So I'm trying to solve this problem and I came up with a brute force solution. I was wondering how can i make it more efficient ?

Problem: Suppose i have resources and integer that denotes at what time it was used in an array. Now we have a variable 'window' = 3. I need to find the resource which was accessed the most in a particular window ( 3 in this case ). Example

{
  "r1": [1,8,3,2,5,6,4] 
  "r2": [1,3,5,6,2] 
}

Output

resource 1 and the count is 4. because between window 3 to 6 it was accessed 4 times

My solution is I would sort every resources and loop over every resource window and then have another loop which runs on the next element. I would count if the element falls in window and maintain a max count variable as well. I think the time complexity would be n^2 * log n + (n*m) (please correct me if i'm wrong) because i will have to sort each resources ( n) and go over m elements ( m is length of resource list)

$\endgroup$
8
  • 1
    $\begingroup$ I don't understand your problem. Why do you write "# 1 2 3 4 5 6 8" for resource 1 while there is no 5 in the list? What do you mean by a "window"? Why do you count between window 3 and 6? $\endgroup$
    – xskxzr
    Mar 23, 2022 at 2:29
  • $\begingroup$ @xskxzr sorry, it was just for my mental note. It was just the sorted version of the array. So window is the amount of seconds. So the problem says, find the resource that was accessed the most in 3 seconds. $\endgroup$
    – Yolo
    Mar 23, 2022 at 2:54
  • $\begingroup$ Then if the list does not contain 5, isn't the count is 3 since resource 1 is accessed 3 times (3, 4, 6) between window 3 and 6? $\endgroup$
    – xskxzr
    Mar 23, 2022 at 2:59
  • $\begingroup$ @Yolo, your window in the given is 3, which I assume means the you want to check resource usage starting at time 3. Why is the end time 6? $\endgroup$
    – Russel
    Mar 23, 2022 at 3:06
  • $\begingroup$ @xskxzr Sorry, the input was wrong. There is a 5 in the resource 1 that's why the count is 4 $\endgroup$
    – Yolo
    Mar 23, 2022 at 3:46

1 Answer 1

1
$\begingroup$

You can use the sliding window technique (also known as "Two Pointers") to traverse the array in $O(N)$.

Here's a full working C++ code.

#include <bits/stdc++.h>
using namespace std;

int count(const int window, vector<int> resource) {
  sort(resource.begin(), resource.end());

  int ans = 0;

  for (int i = 0, j = 0; i < resource.size(); i++) {
    for (; j < resource.size(); j++) {
      int diff = j - i + 1;
      if (resource[j] - resource[i] > window) break;
      ans = max(ans, diff);
    }
  }

  return ans;
}

int main() {
  int window = 3;

  cout << count(window, vector<int>{1, 8, 3, 2, 5, 6, 4}) << endl;
  cout << count(window, vector<int>{1, 3, 5, 6, 2}) << endl;
  cout << count(window, vector<int>{1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 7}) << endl;
  cout << count(1, vector<int>{1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 7}) << endl;
}


Output is:

4
3
14
10

I'm not sure if this is what you were looking for. The last value outputted is 10 because of the 1, 1, 1, 1, 1, 1, 2, 2, 2, 2. This algorithm considers that sequence to be in a window of 1. If you need to change that, some tweaks would be needed.

The total complexity for each independent resource is $O(N \log N)$ because of the sort.

Also, since every resource has to be processed independently with this algorithm, you can execute them in parallel (several threads) and then join all the results. This will improve the runtime a bit.

$\endgroup$
1
  • 3
    $\begingroup$ This is exactly what the OP had in mind for an algorithm? (But it being more concise and with the correct complexity) $\endgroup$
    – nir shahar
    Mar 23, 2022 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.