1

so I have a task. I've been given n numbers and m intervals and I need to figure out how many numbers are in the m i-th interval. I've written some code with a complexity of O(n*m), though I need to optimize it more. Any help? Code:

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

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    int n,m,temp,temp1;
    vector <pair<int, int>> uogienes;
    vector <int> erskeciai;

cin >> n >> m;
for (int i = 0; i< n; i++){
    cin>>temp;
    erskeciai.push_back(temp);
}
temp = 0;
for (int i = 0; i<m; i++){
    cin>> temp >> temp1;
    uogienes.push_back(make_pair(temp, temp1));
}
for(int i = 0; i<m; i++){
        temp=0;
    for(int h = 0; h<n; h++){
       if(uogienes[i].first <= erskeciai[h] && uogienes[i].second >= erskeciai[h]){
        temp++;
        }
    }
cout  << temp << "\n";
}
return 0;

}

Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
Mike Leedlow
  • 37
  • 4
  • 3
    Do your code work? If it does, and all you want are hints about possible optimizations, then you should post on https://codereview.stackexchange.com/ instead. But first please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) as well as [Why is “using namespace std” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Some programmer dude Jan 04 '18 at 12:29
  • Yes, it does work, just wrongly inserted code, since I'm on mobile. I only use them because I'm a competitive programmer, so time is precious. @Some – Mike Leedlow Jan 04 '18 at 12:38
  • 2
    Doing "competetive" programming will only teach you competetive programming. If you really want to learn how to program C++ [get a good beginners book or two](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list), and continue from there. Or go to school/college/university. And actually, including `` will include more header files than you possibly need, making the compilation of your code much ***slower***! – Some programmer dude Jan 04 '18 at 12:42
  • HInts: 1. sort the numbers 2. use `std::lower_bound` – DAle Jan 04 '18 at 12:55
  • your problem is perfect for "Divide and conquer algorithm" – Zharios Jan 04 '18 at 13:16

1 Answers1

0

As DAle already noted.

You can first sort the n numbers. A good algorithm, like merge or heap sort, will give you a complexity O(n*log(n)).

After that you need to use search algorithm for both your 'first' and 'second' parts of each interval. Depending on the algorithm, the complexity should be around O(log(n)) - std::lower_bound has complexity of O(log(n)) when working on sorted data, so its good enough. Or that will be O(m*log(n)) for all intervals.

Comparing the result of the search will give you the amount of numbers in each interval.

In total you'll have around O((m+n)*log(n)).

Smoothgoal
  • 25
  • 7