Fastest way to find if a lot numbers are in multiple intervals
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
3
down vote
favorite
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 times 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;
c++ algorithm sorting
add a comment |Â
up vote
3
down vote
favorite
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 times 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;
c++ algorithm sorting
Please fix the spacing. The easiest way is to paste in the correctly-spaced code, select the whole thing, and then click on the "Code" icon in the toolbar or press control-K.
â Snowbody
Jan 5 at 17:10
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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 times 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;
c++ algorithm sorting
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 times 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;
c++ algorithm sorting
edited Jan 4 at 14:25
Null
8572920
8572920
asked Jan 4 at 13:44
Jacob
161
161
Please fix the spacing. The easiest way is to paste in the correctly-spaced code, select the whole thing, and then click on the "Code" icon in the toolbar or press control-K.
â Snowbody
Jan 5 at 17:10
add a comment |Â
Please fix the spacing. The easiest way is to paste in the correctly-spaced code, select the whole thing, and then click on the "Code" icon in the toolbar or press control-K.
â Snowbody
Jan 5 at 17:10
Please fix the spacing. The easiest way is to paste in the correctly-spaced code, select the whole thing, and then click on the "Code" icon in the toolbar or press control-K.
â Snowbody
Jan 5 at 17:10
Please fix the spacing. The easiest way is to paste in the correctly-spaced code, select the whole thing, and then click on the "Code" icon in the toolbar or press control-K.
â Snowbody
Jan 5 at 17:10
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
Review
Please don't use using namespace;
on the gobal scope. It's considered bad practice. Next, try to keep the scope of your variables smaller. Also indent your code properly to make it easier for you (and others) to see the program flow.
Don't include bits/c++
. It's not a standard header. It's somewhat OK in programming challenges, but you should use the proper includes in your real/production code.
If you use a smaller scope for your variables, you will also be able to use better names for them, for example lower
instead of temp
and upper
instead of temp1
.
If we apply these changes (and translate your names into English), we end up with
#include <iostream>
#include <utility>
#include <vector>
int main()
std::cin.tie(0);
ios_base::sync_with_stdio(0);
std::cout.tie(0);
std::vector<std::pair<int, int>> ranges;
std::vector<int> numbers;
int number_count, range_count;
std::cin >> number_count >> range_count;
for (int i = 0; i < number_count; i++)
int number;
std::cin >> number;
numbers.push_back(number);
for (int i = 0; i < range_count; i++)
int lower, upper;
std::cin >> lower >> upper;
ranges.push_back(lower, upper);
for(int i = 0; i < range_count; i++)
int count = 0;
for(int h = 0; h <number_count; h++)
if(ranges[i].first <= numbers[h] && ranges[i].second >= numbers[h])
count++;
std::cout << count << "n";
return 0;
It would be even better to use the proper types and more functions for I/O.
Performance
Instead of $mathcal O(nm)$, you can get $mathcal O((n+m) log n)$ if you std::sort
the numbers and then use std::lower_bound
and std::upper_bound
.
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Review
Please don't use using namespace;
on the gobal scope. It's considered bad practice. Next, try to keep the scope of your variables smaller. Also indent your code properly to make it easier for you (and others) to see the program flow.
Don't include bits/c++
. It's not a standard header. It's somewhat OK in programming challenges, but you should use the proper includes in your real/production code.
If you use a smaller scope for your variables, you will also be able to use better names for them, for example lower
instead of temp
and upper
instead of temp1
.
If we apply these changes (and translate your names into English), we end up with
#include <iostream>
#include <utility>
#include <vector>
int main()
std::cin.tie(0);
ios_base::sync_with_stdio(0);
std::cout.tie(0);
std::vector<std::pair<int, int>> ranges;
std::vector<int> numbers;
int number_count, range_count;
std::cin >> number_count >> range_count;
for (int i = 0; i < number_count; i++)
int number;
std::cin >> number;
numbers.push_back(number);
for (int i = 0; i < range_count; i++)
int lower, upper;
std::cin >> lower >> upper;
ranges.push_back(lower, upper);
for(int i = 0; i < range_count; i++)
int count = 0;
for(int h = 0; h <number_count; h++)
if(ranges[i].first <= numbers[h] && ranges[i].second >= numbers[h])
count++;
std::cout << count << "n";
return 0;
It would be even better to use the proper types and more functions for I/O.
Performance
Instead of $mathcal O(nm)$, you can get $mathcal O((n+m) log n)$ if you std::sort
the numbers and then use std::lower_bound
and std::upper_bound
.
add a comment |Â
up vote
3
down vote
Review
Please don't use using namespace;
on the gobal scope. It's considered bad practice. Next, try to keep the scope of your variables smaller. Also indent your code properly to make it easier for you (and others) to see the program flow.
Don't include bits/c++
. It's not a standard header. It's somewhat OK in programming challenges, but you should use the proper includes in your real/production code.
If you use a smaller scope for your variables, you will also be able to use better names for them, for example lower
instead of temp
and upper
instead of temp1
.
If we apply these changes (and translate your names into English), we end up with
#include <iostream>
#include <utility>
#include <vector>
int main()
std::cin.tie(0);
ios_base::sync_with_stdio(0);
std::cout.tie(0);
std::vector<std::pair<int, int>> ranges;
std::vector<int> numbers;
int number_count, range_count;
std::cin >> number_count >> range_count;
for (int i = 0; i < number_count; i++)
int number;
std::cin >> number;
numbers.push_back(number);
for (int i = 0; i < range_count; i++)
int lower, upper;
std::cin >> lower >> upper;
ranges.push_back(lower, upper);
for(int i = 0; i < range_count; i++)
int count = 0;
for(int h = 0; h <number_count; h++)
if(ranges[i].first <= numbers[h] && ranges[i].second >= numbers[h])
count++;
std::cout << count << "n";
return 0;
It would be even better to use the proper types and more functions for I/O.
Performance
Instead of $mathcal O(nm)$, you can get $mathcal O((n+m) log n)$ if you std::sort
the numbers and then use std::lower_bound
and std::upper_bound
.
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Review
Please don't use using namespace;
on the gobal scope. It's considered bad practice. Next, try to keep the scope of your variables smaller. Also indent your code properly to make it easier for you (and others) to see the program flow.
Don't include bits/c++
. It's not a standard header. It's somewhat OK in programming challenges, but you should use the proper includes in your real/production code.
If you use a smaller scope for your variables, you will also be able to use better names for them, for example lower
instead of temp
and upper
instead of temp1
.
If we apply these changes (and translate your names into English), we end up with
#include <iostream>
#include <utility>
#include <vector>
int main()
std::cin.tie(0);
ios_base::sync_with_stdio(0);
std::cout.tie(0);
std::vector<std::pair<int, int>> ranges;
std::vector<int> numbers;
int number_count, range_count;
std::cin >> number_count >> range_count;
for (int i = 0; i < number_count; i++)
int number;
std::cin >> number;
numbers.push_back(number);
for (int i = 0; i < range_count; i++)
int lower, upper;
std::cin >> lower >> upper;
ranges.push_back(lower, upper);
for(int i = 0; i < range_count; i++)
int count = 0;
for(int h = 0; h <number_count; h++)
if(ranges[i].first <= numbers[h] && ranges[i].second >= numbers[h])
count++;
std::cout << count << "n";
return 0;
It would be even better to use the proper types and more functions for I/O.
Performance
Instead of $mathcal O(nm)$, you can get $mathcal O((n+m) log n)$ if you std::sort
the numbers and then use std::lower_bound
and std::upper_bound
.
Review
Please don't use using namespace;
on the gobal scope. It's considered bad practice. Next, try to keep the scope of your variables smaller. Also indent your code properly to make it easier for you (and others) to see the program flow.
Don't include bits/c++
. It's not a standard header. It's somewhat OK in programming challenges, but you should use the proper includes in your real/production code.
If you use a smaller scope for your variables, you will also be able to use better names for them, for example lower
instead of temp
and upper
instead of temp1
.
If we apply these changes (and translate your names into English), we end up with
#include <iostream>
#include <utility>
#include <vector>
int main()
std::cin.tie(0);
ios_base::sync_with_stdio(0);
std::cout.tie(0);
std::vector<std::pair<int, int>> ranges;
std::vector<int> numbers;
int number_count, range_count;
std::cin >> number_count >> range_count;
for (int i = 0; i < number_count; i++)
int number;
std::cin >> number;
numbers.push_back(number);
for (int i = 0; i < range_count; i++)
int lower, upper;
std::cin >> lower >> upper;
ranges.push_back(lower, upper);
for(int i = 0; i < range_count; i++)
int count = 0;
for(int h = 0; h <number_count; h++)
if(ranges[i].first <= numbers[h] && ranges[i].second >= numbers[h])
count++;
std::cout << count << "n";
return 0;
It would be even better to use the proper types and more functions for I/O.
Performance
Instead of $mathcal O(nm)$, you can get $mathcal O((n+m) log n)$ if you std::sort
the numbers and then use std::lower_bound
and std::upper_bound
.
answered Jan 4 at 14:27
Zeta
14.3k23267
14.3k23267
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f184282%2ffastest-way-to-find-if-a-lot-numbers-are-in-multiple-intervals%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Please fix the spacing. The easiest way is to paste in the correctly-spaced code, select the whole thing, and then click on the "Code" icon in the toolbar or press control-K.
â Snowbody
Jan 5 at 17:10