We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. C++
  3. Other Concepts
  4. Attending Workshops
  5. Discussions

Attending Workshops

  • farhang_amary
     + 0 comments

    I just tried a new solution in C++. I found that using a deque with workshops sorted by start time and duration is more convenient. First, store all workshops inside that deque, sort them, and then use a helper deque to get the maximum number of workshops with no overlap. The trick is to take the workshop with the earliest end time if they overlap. My code works and passed all tests successfully; however, it can be further improved.

    struct Workshop
{
  time_t start_time, end_time;
  int duration;
  Workshop(int s_time, int dur) : start_time{s_time},
                                  duration{dur},
                                  end_time{s_time + dur} {}
};
bool compare_w(Workshop *w1, Workshop *w2)
{
  if (w1->start_time == w2->start_time)
    return w1->duration < w2->duration;
  return w1->start_time < w2->start_time;
}

struct Available_Workshops
{
  int n;
  deque<Workshop *> workshops;
  Available_Workshops(int i) : n{i} {}
};

Available_Workshops *initialize(int start_times[], int duration[], int n)
{
  Available_Workshops *workshops = new Available_Workshops(n);
  for (int i = 0; i < n; ++i)
  {
    Workshop *w = new Workshop(start_times[i], duration[i]);
    workshops->workshops.push_back(move(w));
  }
  sort(workshops->workshops.begin(), workshops->workshops.end(), compare_w);
  return workshops;
}

int CalculateMaxWorkshops(Available_Workshops *ptr)
{
  deque<Workshop *> ws;
  ws.push_front(ptr->workshops.front());
  ptr->workshops.pop_front();
  while (!ptr->workshops.empty())
  {
    auto cw = ptr->workshops.front();
    auto nw = ws.front();

    if (cw->start_time >= nw->end_time)
    {
      ws.push_front(cw);
      ptr->workshops.pop_front();
      continue;
    }

    if (cw->start_time == nw->start_time)
    {
      ptr->workshops.pop_front();
      continue;
    }
    if (cw->start_time <= nw->end_time && cw->end_time <= nw->end_time)
    {
      ws.pop_front();
      ws.push_front(cw);
      ptr->workshops.pop_front();
      continue;
    }
    ptr->workshops.pop_front();
  }
  int cnt = ws.size();

  for (Workshop *w : ws)
  {
    delete w;
  }
  delete ptr;
  return cnt;
}