Fastest way to find if a lot numbers are in multiple intervals

The name of the pictureThe name of the pictureThe name of the pictureClash 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;







share|improve this question





















  • 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
















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;







share|improve this question





















  • 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












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;







share|improve this question













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;









share|improve this question












share|improve this question




share|improve this question








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
















  • 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










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.






share|improve this answer





















    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );








     

    draft saved


    draft discarded


















    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






























    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.






    share|improve this answer

























      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.






      share|improve this answer























        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.






        share|improve this answer













        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.







        share|improve this answer













        share|improve this answer



        share|improve this answer











        answered Jan 4 at 14:27









        Zeta

        14.3k23267




        14.3k23267






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            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













































































            Popular posts from this blog

            Greedy Best First Search implementation in Rust

            Function to Return a JSON Like Objects Using VBA Collections and Arrays

            C++11 CLH Lock Implementation