Find the max number in list after m operations between indices a and b Given the problem:


  You are provided a list of N elements all initialized to 0, and a list of M operations. Where each m in M consists of 3 elements a, b, and k. For each m in M add k to all indices in the range [a, b]. At the end of all M operations print out the max.


I have two implementations, one of which is faster because of constant time lookups, whereas the other can be more memory usage efficient. I am looking for a third implementation which might run faster than the previous two.

#include &lt;cassert&gt;
#include &lt;climits&gt;
#include &lt;cstdlib&gt;
#include &lt;ctime&gt;
#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;map&gt;
#include &lt;sstream&gt;
#include &lt;string&gt;
#include &lt;vector&gt;

void run_tests1(int N, int M, const std::vector&lt;std::vector&lt;int&gt; &gt; &amp;a_b_k)
{
    std::vector&lt;int&gt; LIST(N);
    int max = INT_MIN;

    for (int m = 0; m &lt; M; ++m) {
        int a = a_b_k[m][0];
        int b = a_b_k[m][1];
        int k = a_b_k[m][2];

        clock_t now = clock();
        for (int i = a; i &lt;= b; ++i) {
            LIST[i] += k;
            if (LIST[i] &gt; max) {
                max = LIST[i];
            }
        }
        clock_t end = clock() - now;
        std::cout &lt;&lt; "Took " &lt;&lt; ((float)end / CLOCKS_PER_SEC) &lt;&lt; " on "
          &lt;&lt; __FUNCTION__ &lt;&lt; " to insert " &lt;&lt; (b - a + 1) &lt;&lt; std::endl;
    }
}

void run_tests2(int /*N*/, int M, const std::vector&lt;std::vector&lt;int&gt; &gt; &amp;a_b_k)
{
    std::map&lt;int, int&gt; LIST;
    int max = INT_MIN;

    for (int m = 0; m &lt; M; ++m) {
        int a = a_b_k[m][0];
        int b = a_b_k[m][1];
        int k = a_b_k[m][2];

        clock_t now = clock();
        for (int i = a; i &lt;= b; ++i) {
            std::pair&lt;std::map&lt;int, int&gt;::iterator, bool&gt; status =
              LIST.insert(std::make_pair(i, 0));

            status.first-&gt;second += k;
            if (status.first-&gt;second &gt; max) {
                max = status.first-&gt;second;
            }
        }
        clock_t end = clock() - now;
        std::cout &lt;&lt; "Took " &lt;&lt; ((float)end / CLOCKS_PER_SEC) &lt;&lt; " on "
          &lt;&lt; __FUNCTION__ &lt;&lt; " to insert " &lt;&lt; (b - a + 1) &lt;&lt; std::endl;
    }
}

void run_tests3(int N, int M, const std::vector&lt;std::vector&lt;int&gt; &gt; &amp;a_b_k)
{
    // Choose Data Structure
    int max = INT_MIN;

    for (int m = 0; m &lt; M; ++m) {
        int a = a_b_k[m][0];
        int b = a_b_k[m][1];
        int k = a_b_k[m][2];

        clock_t now = clock();
        // Run Algorithm
        clock_t end = clock() - now;
        std::cout &lt;&lt; "Took " &lt;&lt; ((float)end / CLOCKS_PER_SEC) &lt;&lt; " on "
          &lt;&lt; __FUNCTION__ &lt;&lt; " to insert " &lt;&lt; (b - a + 1) &lt;&lt; std::endl;
    }
}

int main()
{
    const int K = 1000;
    const int N = 10000000;
    const int M = 10;
    std::vector&lt;std::vector&lt;int&gt; &gt; data(M);

    for (int m = 0; m &lt; M; ++m) {
      data[m].resize(3);
      data[m][0] = rand() % N;
      data[m][1] = rand() % N;
      data[m][2] = rand() % K;

      if (data[m][0] &gt; data[m][1]) {
          std::swap(data[m][0], data[m][1]);
      }
    }

    run_tests1(N, M, data);
    run_tests2(N, M, data);
    run_tests3(N, M, data);
}
For the record, don't ask us to write code for you. Writing the code is your responsibility; we will just critique it.


Why are you concerned about how long it takes to process each operation? The only thing that matters is the overall time and space requirement, and it's not a given that the best solution is going to operate by processing each operation in sequence. Thus, the timing does not belong in the loop. And I would even make the case that the timing does not belong in the run_testsn() functions. The timing belongs in your main function, which will call each of the run_testsn() in sequence. Each function should have one purpose only. It shouldn't be "Do this in this particular way and then time subunits of it.".
You've got a lot of unnecessary #includes. That just clutters up the code. Only use the ones you need.
Kudos to you for qualifying your C++ types with std::. But as @Morwenn said, don't forget to do it for functions from the C standard library too.
Is it necessary to take your input as a vector of vectors? It would make a lot more sense to build a struct with members int a; int b; int k; and then pass vectors of that around.
A map is pretty good for representing a sparse array; there are several other libraries out there that do better. See https://stackoverflow.com/questions/4306/what-is-the-best-way-to-create-a-sparse-array-in-c and https://stackoverflow.com/questions/21310680/sparse-array-in-c
You have two (soon-to-be three) functions that take the same parameter list and do the same thing. This looks like a job for an abstract base class (specifying the interface/params) and three subclasses of that class that each have implementations.
In run_tests2 you have


       std::pair&lt;std::map&lt;int, int&gt;::iterator, bool&gt; status =
         LIST.insert(std::make_pair(i, 0));

       status.first-&gt;second += k;



What's wrong with LIST[i] += k;? If the item doesn't exist yet, it will be auto-created with the default value (0). (And even if not, please declare it using auto status = as that type is just plain ugly and doesn't add anything. You're using C++11, take advantage of ways it can produce better code)