1
\$\begingroup\$

This problem is from MIT Course and I have implemented it in C++. Please review and suggest improvements.

There is a party to celebrate celebrities that you get to attend because you won a ticket at your office lottery. Because of the high demand for tickets you only get to stay for one hour but you get to pick which one since you received a special ticket. You have access to a schedule that lists when exactly each celebrity is going to attend the party. You want to get as many pictures with celebrities as possible to improve your social standing. This means you wish to go for the hour when you get to hob-nob with the maximum number of celebrities and get selfies with each of them.

We are given a list of intervals that correspond to when each celebrity comes and goes. Assume that these intervals are [i, j), where i and j correspond to hours. That is, the interval is closed on the left hand side and open on the right hand side. This just means that the celebrity will be partying on and through the ith hour, but will have left when the jth hour begins. So even if you arrive on dot on the th hour, you will miss this particular celebrity.

Here’s an example:

example

When is the best time to attend the party? That is, which hour should you go to?

#include <iostream>
#include <vector>
#include <algorithm>

struct range
{
    int start = 0;
    int end = 0;

    range() = default;
    range(int start_time, int end_time):
        start(std::move(start_time)),
        end(std::move(end_time))
        {}
};

int celeb_density(std::vector<range>& schedule)
{
    //sort according to start_time
    auto by_start_time = [](const range &a, const range &b)
    {
        return a.start < b.start;
    };
    std::sort(schedule.begin(), schedule.end(), by_start_time);

    int party_start = schedule[0].start;   //Party start time
    int party_end = schedule[schedule.size()-1].end;  //Party end time
    int max_count = 0, curr_max = 0, best_time, curr_best_time;

    int i = party_start;
    while (i < party_end)
    {
        for (int j = 0; j < schedule.size(); ++j)
        {
            if (i == schedule[j].start)
            {
                curr_max++;
                curr_best_time = i;
            }
            else if (i < schedule[j].start)
            {
                break;
            }

            if (i == schedule[j].end)
            {
                curr_max--;
            }
        }
        if (curr_max > max_count)
        {
            max_count = curr_max;
            best_time = curr_best_time;
        }
        i++;
    }
    return best_time;
}

int main()
{
    std::vector<range> schedule;

    int number_of_celebs;
    std::cout << "Enter number of celebrities attending party: ";
    std::cin >> number_of_celebs;

    std::cout << "Enter entry time and exit time for a celebrity\n";
    for (int i = 0; i < number_of_celebs; ++i)
    {
        int s, e;
        std::cin >> s >> e;
        schedule.push_back(range(s, e));
    }

    int best_time = celeb_density(schedule);
    std::cout << "Best time to attend party is from " << best_time << " to " << best_time + 1 << "\n";
}
\$\endgroup\$
  • \$\begingroup\$ You're not getting what std::move is all about ;) \$\endgroup\$ – Carlo Wood Sep 29 at 13:37
  • \$\begingroup\$ @CarloWood do write an answer if you think you can provide a useful review; it doesn't need to be long, it just needs to make a valuable and unique contribution, and since I barely know C++, if you can make a comment as someone who does, that would be great. \$\endgroup\$ – VisualMelon Sep 29 at 16:18
4
\$\begingroup\$

Good to see you're not doing a using namespace std ;). Of course it doesn't really hurt in a source file (.cpp) (it does in a header file!), but even then that is still considered bad practice. My personal reason to just always type the namespace is because it makes code easier to read (you know what is part of a namespace and which and don't have to guess that) and it is easier to search with regular expressions and the like.

While the standard does not use class names that begin with an upper case letter, many good coders do. It allows you - in fact - to have your own classes to stand out better, and using both upper case and lower case adds more state to your namespace (aka, less collisions). For example, you can call your class Range and a Range variable range.

Also for both, readability and regular expression searches, I strongly recommend only to use complete English words for any class, variable or function name and never resort to abbreviations. The only exceptions to this rule are local variables that are so local (used in a scope of only a few lines) that you can easily see their declaration and use on one screen and where their meaning is mostly irrelevant(!). For example a counter of a for loop can be called i if you must.

Also for ease of regular expression search and understandability (maintenance) of code it is a good idea to use the same name for variables that contain the same object (you copied a value from one to the other). Ok, that is normally not possible unless you pass them as function argument (you can't write range = range) but you'll surprised how often it is; for example use range_end for every variable that means "the end of a range". Why am I mentioning this? Well, this is the reason that class member variables often have a prefix (either M_ or m_ or something. I use m_. That way you avoid collisions with local variables with the same name, and member functions with the same name.

C++ provides classes with a reason: to write Object Oriented code. Encapsulation is part of that. In almost all cases your class member variables should be private!

For (ostream based) debugging output, it is a good idea to make every class writable to an ostream.

std::move is just a cast, from an lvalue reference to an rvalue reference, and only useful when you pass the result to a function that takes an rvalue reference (aka, you pick the right overloaded function with it). Where you used std::move the argument isn't an lvalue reference, nor do you pass the result of the std::move to a function that accepts an rvalue reference, so using std::move there is nonsense. PS By convention a moved object (whose rvalue reference was passed to a function) should only be destructed afterwards (in all but exceptional cases). So if you cast an lvalue reference to an rvalue reference then that variable had better be passed in as an rvalue reference in the first place. The typical use case therefore looks as follows:

void bar(Bar&& bar);

void foo(Bar&& bar)
{
  // Here bar is an lvalue reference!
  bar(std::move(bar));
  // Now 'bar' may no longer used, only destructed (by convention:
  // it is like that because one would expect that bar() makes it so.
}

This would work fine when foo() took an lvalue reference (foo(Bar& bar)) but then the caller of foo wouldn't be aware of the fact that bar was moved and could "accidently" use bar still after returning from foo(bar).

Combining what we learned so far, I arrive at the follow code for Range:

class Range
{
  private:
    int m_start_time = 0;
    int m_end_time = 0;

  public:
    Range() = default;
    Range(int start_time, int end_time) :
        m_start_time(start_time),
        m_end_time(end_time)
        { }

    int start_time() const { return m_start_time; }
    int end_time() const { return m_end_time; }

    friend std::ostream& operator<<(std::ostream& os, Range const& range);
};

Well, that's enough for today. I'll finish with my own stab at celeb_density:

int celeb_density(std::vector<Range> const& schedule)
{
    // Do not pass an empty schedule.
    assert(!schedule.empty());          // #include <cassert>

    std::array<unsigned int, 24> hours; // #include <array>
    hours.fill(0);

    int best_time = schedule[0].start_time();
    int max_celebs = 1;
    for (auto range : schedule)
      for (int hour = range.start_time(); hour < range.end_time(); ++hour)
        if (++hours[hour] > max_celebs)
        {
          ++max_celebs;
          best_time = hour;
        }

    return best_time;
}
\$\endgroup\$
3
\$\begingroup\$

General Stuff

I would use a for-loop for i: with the while loop you've just ended up moving the i++ far from the condition logic, which makes it that little bit harder to understand quickly. I'd also rename it to time or t: i is typical for indexing, which might give the wrong impression.

I don't really know C++, so I might be falling into a trap, but I would consider removing range's parameterless constructor so that it's harder to misuse.

Your celeb_density method will crash violently if the schedule is empty. You should probably detect this case and fail in a helpful manner. celeb_density is not great name: it tells me nothing about what it does or what it returns.

Your main method (though I don't suppose you are too worried about this) doesn't perform any validation, so I can, for example, request a negative number of entries, and it will happily ask me to enter a start and end time before it crashes in celeb_density. It only prompts for a range once (which is confusing), and it doesn't complain if I enter a range where start > end. Range could also throw if start > end, which would ensure that the code producing the invalid input throws rather than algorithms producing meaningless results.

Your vector has a size type of size_t, so you should ideally make j that same type.

Performance and Scalability

Using a sort to find the start is excessive, because you algorithm doesn't care about the order in the schedule: you can find these with a linear scan. It also means you have modified the input, which the caller might not appreciate.

Your method (ignoring the sort) has a worst case time complexity of O(n*m) where n is the size of the schedule, and m is the time-space between the start and end of the schedule. In terms of scalability, this isn't ideal, but its a stupid little example without a specification for performance, so this might not matter.

However, we can achieve a O(n log(n)) worst case time complexity (which would already have because of the sort, but that is trivially removed). A sort will be in order, but first break the events into two entries: an incrementing entry and a decrementing entry. You can then sort these and just loop over them incrementing and decrementing as you go, keeping track of the 'best time' as you already are. The only detail is that you need to sort the decrementing events before the incrementing events or otherwise deal with the situation where there are arrivals and departures on the same hour.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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