C++ Hackerrank 购票优化

Hackerrank Buying show tickets Optimization

提问by Rohan Kumar

I encountered this problem on an online screening test of a company a few days ago. The problem statement reads like this:

前几天在某公司的一次网上筛选测试中遇到了这个问题。问题陈述如下：

There are n people standing in line to buy show tickets.Due to high demand, the venue sells tickets according to the following rules:

• The person at the head of the line can buy exactly one ticket and must then exit the line.
• if a person needs to purchase additional tickets,they must re-enter the end of the line and wait to be sold their next ticket(assume exit and re-entry takes zero seconds).
• Each ticket sale takes exactly one second.

We express initial line of n people as an array, tickets = [tickets0, tickets1 ... ticketsN-1], where ticketsi denotes the number of tickets person i wishes to buy. If Jesse is standing at a position p in this line, find out how much time it would take for him to buy all tickets. Complete the waiting time function in the editor below. It has two parameters:

1. An array, tickets, of n positive integers describing initial sequence of people standing in line. Each ticketsi describes number of tickets that a person waiting at initial place.

2. An integer p, denoting Jesse's position in tickets.

   Sample Input 5 2 6 3 4 5 2 Sample Output 12 Sample Input 4 5 5 2 3 3 Sample Output 11

排队购票的人数为n人，因需求旺盛，场馆按以下规则售票：

• 排在队伍最前面的人只能购买一张票，然后必须退出队伍。
• 如果一个人需要购买额外的票，他们必须重新进入队伍的末尾并等待他们的下一张票被出售（假设退出和重新进入需要零秒）。
• 每次售票只需要一秒钟。

我们将最初的 n 人行表示为一个数组，ticket = [tickets0,tickets1 ... ticketN-1]，其中 ticketi 表示我希望购买的票数。如果 Jesse 站在这条线上的位置 p，找出他买完所有门票需要多长时间。在下面的编辑器中完成等待时间功能。它有两个参数：

1. 一个由 n 个正整数组成的数组票证，描述了排队的人的初始序列。每张票i 描述了一个人在初始位置等待的票数。

2. 整数 p，表示 Jesse 在门票中的位置。

   样本输入 5 2 6 3 4 5 2 样本输出 12 样本输入 4 5 5 2 3 3 样本输出 11

During the time of the test, i came up with this simple approach which passed most of the test cases but was getting timed out on a few test cases:

在测试期间，我想出了这个简单的方法，它通过了大部分测试用例，但在一些测试用例上超时：

long waitingTime(vector<int> tickets, int p) {
  // bool flag indicates whether it's Jesse or not
  queue<pair<int, bool> > aQueue;

  for(int i = 0; i < tickets.size(); i++) {
    aQueue.push(make_pair(tickets[i], i == p));
  }

  long long nTime = 1;
  while(!aQueue.empty()) {
    pair<int, bool> aItem = aQueue.front();
    aQueue.pop();
    nTime++;
    if(aItem.first == 1 && aItem.second == true)
      break;
    else if(aItem.first > 1) {
      aQueue.push(make_pair(aItem.first-1, aItem.second));
    }
  }
  return nTime-1;
}

But i'm not able to find a different approach to solve this problem. I think there is some other way without having to simulate the whole queue flow. I would really appreciate if someone could provide me with the right approach of solving this. Thanks in advance!

但我找不到解决这个问题的不同方法。我认为还有其他一些方法而不必模拟整个队列流。如果有人能为我提供解决此问题的正确方法，我将不胜感激。提前致谢！

回答by Abhishek Kulkarni

All the test cases on HackerRank are passed. The simplest solution to this is -

HackerRank 上的所有测试用例都通过了。对此最简单的解决方案是-

def waitingTime(tickets, p):
    total_steps = tickets[p]
    first_half = tickets[:p]
    second_half = tickets[p+1:]

    for num in first_half:
        if num < tickets[p]:
            total_steps += num
        else:
            total_steps += tickets[p]

    for num in second_half:
        if num < tickets[p]:
            total_steps += num
        else:
            total_steps += tickets[p] - 1

    return total_steps

Explanation -

解释 -

1. Divide list into two halves. People standing ahead of Jesse and persons standing behind Jesse.
2. Check with each person in both the halves - how many tickets that person wants to buy.
3. Lets consider first half
4. If the person wants to buy less number of tickets than that of Jesse - the person will visit the ticket window till he buy the tickets before Jesse. So add his number of tickets to the total unit time
5. If the person wants to buy more or the equal tickets than Jesse then he will visit ticket window before Jesseexactly the same number of times that Jesse visits the ticket window. So add Jesse's tickets count to the total unit time - which is equal to the person's ticket count which he buys before Jesse
6. Now consider second half -
7. If the person standing behind Jesse wants to buy more or equal tickets than Jesse, he will visit ticket window one less time than Jesse. So add (Jesse's ticket count - 1) to the total unit time
8. If the person standing behind Jesse wants to buy less tickets than Jesse, then the person will visit ticket window until he buys all his tickets. So add persons total ticket count to the total unit time.
9. Finally, add Jesse's ticket count to the total unit time too, because Jesse will also visit the ticket window until he buys all the tickets that he wants

1. 将列表分成两半。站在杰西前面的人和站在杰西后面的人。
2. 与上下半场的每个人核对 - 该人想要购买多少张门票。
3. 让我们考虑上半年
4. 如果此人希望购买的票数少于 Jesse 的数量 - 该人将访问售票窗口，直到他在 Jesse 之前购买门票。所以把他的票数加到总单位时间
5. 如果此人想要购买比 Jesse 多或相等的票，那么他将在 Jesse 之前访问售票窗口，其次数与 Jesse 访问售票窗口的次数完全相同。所以将 Jesse 的票数加到总单位时间 - 这等于他在 Jesse 之前购买的人的票数
6. 现在考虑下半场——
7. 如果站在 Jesse 后面的人想要购买比 Jesse 多或相等的票，他将比 Jesse 少到售票窗口的时间。所以将 (Jesse 的票数 - 1) 添加到总单位时间
8. 如果站在 Jesse 后面的人想买的票比 Jesse 少，那么这个人会去售票窗口，直到他买完所有的票。因此，将人员总票数添加到总单位时间。
9. 最后，把Jesse的票数也加到总单位时间内，因为Jesse也会去售票窗口，直到他买完所有他想要的票

e.g. Five persons are standing in a queue. Their ticket count is given in the list below. Jesse is standing at 3rd position (list index = 2)

例如，五个人在排队。他们的票数在下面的列表中给出。Jesse 站在第三位（列表索引 = 2）

[2,6,3,4,5]

[2,6,3,4,5]

first half = [2,6] second half = [4,5]

上半场 = [2,6] 下半场 = [4,5]

now consider first half -

现在考虑上半年 -

1. Person#1 wants to buy 2 tickets. Jesse's count (3) is greater than 2. So this person will definitely visit ticket window twice before Jesse. Hence total_unit_time = 2

2. Person#2 wants to buy 6 tickets. Jesse's count (3) is less than 6. So this person will visit ticket window 3 times before Jesse. So total_unit_time = 2+3

1. 人#1 想买两张票。Jesse 的计数 (3) 大于 2。因此此人肯定会在 Jesse 之前两次访问售票窗口。因此 total_unit_time = 2

2. 人#2 想买 6 张票。Jesse 的计数 (3) 小于 6。因此此人将在 Jesse 之前访问售票窗口 3 次。所以 total_unit_time = 2+ 3

now consider second half - 1. Person#1 wants to buy 4 tickets. Jesse's count (3) is less than 4. Now, Jesse will buy his first ticket then the person will get a chance to buy his first ticket. But then Jesse will have to wait for 2 more turns to buy remaining 2 tickets after this person. So total_unit_time = 2+3+(3-1)

现在考虑下半场 - 1. 人#1 想买 4 张票。Jesse 的计数 (3) 小于 4。现在，Jesse 将购买他的第一张票，然后该人将有机会购买他的第一张票。但随后 Jesse 将不得不再等 2 轮才能在此人之后购买剩余的 2 张票。所以 total_unit_time = 2+3+ (3-1)

1. Person#2 wants to buy 5 tickets. Again Jesse will buy his first ticket and will wait for his remaining two turns until this guy buys two tickets. So total_unit_time = 2+3+2+(3-1)

2. 人#2 想买 5 张票。杰西将再次购买他的第一张票，并等待他剩下的两个回合，直到这个人买了两张票。所以 total_unit_time = 2+3+2+ (3-1)

回答by Scheff

Looking at the problem twice, I got the idea that an analytical solution should be possible.

看了两遍这个问题，我觉得应该可以找到一个解析解。

My idea is:

我的想法是：

1. People ibefore Jesse will stay in front of him min{ tickets_i, tickets_Jesse}times.
2. Jesse himself will consume tickets_Jessetimes.
3. People iafter Jesse will stay in front of Jesse min{ tickets_i, tickets_Jesse- 1 }times.

1. 杰西之前的人i将在他面前停留min{ 门票_i，门票_Jesse}次。
2. 杰西本人会消费门票_杰西次。
3. 在 Jesse 之后的人i将留在 Jesse min前面{票_i，票_Jesse- 1 }次。

Thus, it should be possible to simply sum up the numbers in one loop. This would mean O(n) instead of O(n²).

因此，应该可以简单地在一个循环中对数字求和。这意味着 O(n) 而不是 O(n ²)。

As I realized, that the result will also depend on the position of Jesse. However, my results looked somehow different than the sample output. Thus, I implemented a naïve solution (similar to the OP) also. The source waiting-queue.cc:

正如我意识到的，结果也将取决于杰西的位置。但是，我的结果看起来与示例输出有些不同。因此，我也实现了一个简单的解决方案（类似于 OP）。来源waiting-queue.cc：

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

// naive approach

int waitingTimeSim(const std::vector<int> &tickets, int p)
{
  // setup sim. model
  std::queue<std::pair<int, bool> > people;
  for (int i = 0, n = (int)tickets.size(); i < n; ++i) {
    people.push(std::make_pair(tickets[i], i == p));
  }
  // simulation
  int tP = 0;
  for (;;) {
    std::pair<int, bool> person = people.front();
    people.pop();
    --person.first; ++tP; // buy ticket
    if (!person.first) { // if person is done
      if (person.second) return tP; // It's Jesse -> terminate
    } else people.push(person);
  }
}

// analytical approach

int waitingTime(const std::vector<int> &tickets, int p)
{
  int tP = 0, ticketsP = tickets[p];
  for (int i = 0, n = (int)tickets.size(); i < n; ++i) {
    tP += std::min(tickets[i], ticketsP - (i > p));
    // i > p -> people after jesse -> decr. by 1
  }
  return tP;
}

int main()
{
  { std::vector<int> tickets{ 2, 6, 3, 4, 5 };
    for (int p = 0, n = tickets.size(); p < n; ++p) {
      std::cout << "tickets{ 2, 6, 3, 4, 5 }, p = " << p << std::endl;
      int tS = waitingTimeSim(tickets, p);
      std::cout << "simulated t: " << tS << std::endl;
      int t = waitingTime(tickets, p);
      std::cout << "computed t:  " << t << std::endl;
    }
  }
  { std::vector<int> tickets{ 5, 5, 2, 3 };
    for (int p = 0, n = tickets.size(); p < n; ++p) {
      std::cout << "tickets{ 5, 5, 2, 3 }, p = " << p << std::endl;
      int tS = waitingTimeSim(tickets, p);
      std::cout << "simulated t: " << tS << std::endl;
      int t = waitingTime(tickets, p);
      std::cout << "computed t:  " << t << std::endl;
    }
  }
  return 0;
}

I uploaded the source to ideone.com.

我将源上传到ideone.com。

My test session (g++, cygwin, Windows 10):

我的测试会话（g++、cygwin、Windows 10）：

$ g++ -std=c++11 -o waiting-queue waiting-queue.cc 

$ ./waiting-queue.exe 
tickets{ 2, 6, 3, 4, 5 }, p = 0
simulated t: 6
computed t:  6
tickets{ 2, 6, 3, 4, 5 }, p = 1
simulated t: 20
computed t:  20
tickets{ 2, 6, 3, 4, 5 }, p = 2
simulated t: 12
computed t:  12
tickets{ 2, 6, 3, 4, 5 }, p = 3
simulated t: 16
computed t:  16
tickets{ 2, 6, 3, 4, 5 }, p = 4
simulated t: 19
computed t:  19
tickets{ 5, 5, 2, 3 }, p = 0
simulated t: 14
computed t:  14
tickets{ 5, 5, 2, 3 }, p = 1
simulated t: 15
computed t:  15
tickets{ 5, 5, 2, 3 }, p = 2
simulated t: 7
computed t:  7
tickets{ 5, 5, 2, 3 }, p = 3
simulated t: 11
computed t:  11

$

Note:

笔记：

IMHO, the name waitingTime()is a little bit mis-leading because the assignment says clearly that you have to

恕我直言，这个名字waitingTime()有点误导，因为作业清楚地表明你必须

find out how much time it would take for him to buy all tickets.

找出他购买所有门票需要多长时间。

Thus, my implementation counts the waiting time +the time Jesse needs to buy his last ticket.

因此，我的实现计算了等待时间+Jesse 购买最后一张票所需的时间。

Update:

更新：

An often used German phrase says: Who can read is clearly in the advantage. (It doesn't sound so nice and handy in English like in German: „Wer lesen kann, ist klar im Vorteil.“) However, after reading again the comment-answer of Rohan Kumarto my comment-question, I adjusted my sample input to the OP and, suddenly, got the expected output. However, the algorithms didn't change.

一句常用的德语短语说：谁会阅读显然是有优势的。（在英语中听起来不像德语那样好听和方便：„Wer lesen kann, ist klar im Vorteil。“）但是，在再次阅读Rohan Kumar对我的评论问题的评论回答后，我调整了我的样本OP 的输入，突然得到了预期的输出。但是，算法没有改变。

回答by Long Tran

Here is my idea to solve this problem, first take a look at the line. We divide people in 2 groups:
1/ Those stands before pthperson.
2/ Those stands behind pthperosn.
Let's call times- the number of move that pthperson has to take to buy sufficent tickets.

Now considering the first group [tickets0, tickets1, ..., ticketsP-1], ifthere is a person iwho needs to buy the number of tickets smaller than the pthperson, thenjust simply add <ticket i> to times( the duration that pthperson has to wait for the person iuntil he gets out of the line ). Otherwise, in case the amount of buying tickets of person iis bigger than person pth, add <ticket p> to times.

Secondly, the same idea to those who stand behind the pthperson [ticketsP+1, ticketsP+2, ..., ticketsN]. Considering person t(t > p), we add <ticket t> to timesif ticketT< ticketP. Unless person tbuys tickets less then person p, skip the last round so that just add <ticket p- 1 > to times

下面是我解决这个问题的思路，先看看行。我们将人分为 2 组：
1/ 站在第 p个人之前的那些人。
2/ 那些站在pthperosn后面。
让我们调用时间-第 p个人必须采取的行动数量才能购买足够的门票。

现在考虑第一组[ ticket0,tickets1,...,ticketsP-1]，如果有i人需要购买比第p个人少的票数，那么只需将< ticket i>加到times( pth的持续时间人必须等待人i直到他出线）。否则，如果第i个人的购票数量大于第 p个人，则将<票 p>添加到次数。

其次，对站在第p个人后面的那些人 [ ticketP+1, TicketP+2, ..., TicketN] 的想法相同。考虑到人t( t > p)，我们将 < ticket t>添加到时间if ticketT< ticketP。除非人 t买的票少于人 p, 跳过最后一轮，只需将 < ticket p- 1 > 添加到时间

While iterating the lines, dont forget to add ticket pto timeswhenever meet the person p.

在迭代行时，不要忘记在遇到人 p时将票证 p添加到时间。

public static long times( int[] tickets, int p) {
    long times = 0;
    int[] temp = Arrays.copyOf(tickets, tickets.length); //creating this array to check whether the *person i* buy tickets less than *person p*
    for(int i = 0; i < tickets.length; i++ ) {
       temp[i] = tickets[i] - tickets[p];
    }
    for(int i = 0; i < tickets.length; i++ ) {
       if(temp[i] < 0) times += tickets[i];
       else {
          if(i <= p) times += tickets[p];
          else times += tickets[p] - 1;
       }
    }
    return times;
} 

Explain:
Sample Input4 5 5 2 3 3 Sample Output14
p = 4, 14 = 3 + 3 + 2 + 3 + 3

解释：
样本输入4 5 5 2 3 3样本输出14
p = 4, 14 = 3 + 3 + 2 + 3 + 3

回答by legalimpurity

Solution in Java :

Java中的解决方案：

static long waitingTime(int[] tickets, int p) {
        long noOfIterations = 0;
        int ticketBeingProcessed = 0;
        int numberOfParticipantsInLine = tickets.length;
        if(numberOfParticipantsInLine > p)
        {
            while(tickets[p] != 0)
            {
                // The person has already got his ticket and exited the line, just go to the next person, dont increase number of iterations because it took no time
                if(tickets[ticketBeingProcessed] != 0)
                {
                    // ticket being processed got one ticket
                    tickets[ticketBeingProcessed] = tickets[ticketBeingProcessed] -1;
                    // if we have reached the end of the line
                    if(ticketBeingProcessed == numberOfParticipantsInLine -1)
                        ticketBeingProcessed = 0;
                    else
                        ticketBeingProcessed ++;
                    noOfIterations ++;
                }
                else {
                    if (ticketBeingProcessed == numberOfParticipantsInLine - 1)
                        ticketBeingProcessed = 0;
                    else
                        ticketBeingProcessed++;
                }
                Log.d("asd",printArray(tickets));
            }
        }
        return noOfIterations;
    }

回答by Nayeem Zen

Here's the solution I came up with (in Java, but anyone with c++ background can read this code)

这是我想出的解决方案（在 Java 中，但任何具有 C++ 背景的人都可以阅读此代码）

import java.util.Arrays;
import java.util.List;

public class TickerPurcahseTime {
  public static int calculateTimeOptimized(List<Integer> line, int pos) {
    // Minimum time I have to wait is the number of tickets I want to buy.
    int waitingTime = line.get(pos);
    for (int i = 0; i < line.size(); i++) {
      if (i == pos) continue;
      // I will see people -> minimum(how many tickets I need, how many tickets they need).
      waitingTime += (Math.min(line.get(pos), line.get(i)));
      // Unless they were behind me, I got my ticket before them so I need to see them 1 time less.
      if (i > pos) {
        waitingTime--;
      }
    }

    return waitingTime;
  }

  public static void main(String [] args) {
    System.out.println(calculateTimeOptimized(Arrays.asList(5, 5, 2, 3), 3));
  }
}

回答by hari

so here is my O(n) complex and easily understandable solution

所以这是我的 O(n) 复杂且易于理解的解决方案

# people stading before jess will be waiting for t(p) times 
# (or)
# t(i) times (if t(i) - t(p) < 0 this means they will buy less tickets than jess, 
# so they will stand only t(i) times)
#
# people standing beside jess will be waiting for t(p)-1 times
# (or)
# t(i) time (if t(i) - t(p) < 0 )
#
# sum of the above will result in the wating time for jess

def wt(tickets, p):
    sum = 0;
    for i in range(len(tickets)):
        if i<=p :
            if tickets[i]-tickets[p] >= 0 :
                sum += tickets[p];
            else :
                sum += tickets[i];
        else:
            if tickets[i]-(tickets[p]-1) >= 0 :
                sum += tickets[p]-1;
            else:
                sum += tickets[i];
    print(sum);

test cases:

测试用例：

wt([5,5,2,3], 3)

wt([5,5,2,3], 0)

wt([5,5,2,3], 1)

wt([5,5,2,3], 2)

wt([1,1,1,1], 0)

wt([2,6,3,4,5], 2)

wt([2,6,3,4,5], 0)

wt([2,6,3,4,5], 1)

wt([2,6,3,4,5], 3)

wt([2,6,3,4,5], 4)

outputs:

输出：

11

14

15

7

1

12

6

20

16

19

回答by user3569307

For python:

对于蟒蛇：

def function(tickets):
    count = 0
    delta = 0
    for i in range(len(tickets)):
        if tickets[i] < tickets[p]:
            delta+=tickets[p]-tickets[i]
            if i > p:
               delta - = 1

    count = len(tickets) * (tickets[p] - 1) + (p+1) - delta

    return count

回答by Ahmed Benchekroun

Here is simple solution using ruby

这是使用 ruby​​ 的简单解决方案

    def waiting_line(tickets, p)
      user_tickets = tickets[p]
      time = 0
      while user_tickets > 0
        for i in (0...tickets.length)
          break if tickets[p] == 0
          next if (tickets[i] == 0) 
          time +=1 
          tickets[i] -= 1
        end
        user_tickets -=1
      end
      time
    end

回答by Jorge

How about this one in python

python中的这个怎么样

def calculateTickets(l,p):
    j=int(0)#contador de
    while(l[p]!= 0 ):
        i=0
        for i in range (len(l)):
            if(l[p]==0):
                break
            if(l[i]>0):
                l[i]-=1
                j+=1
            i+=1
    print(str(j)+"\n")

回答by Prabhav Nalhe

Here's the simple C++ Solution:

这是简单的 C++ 解决方案：

#include<bits/stdc++.h>
using namespace std;
int waiting_time(int ticket[],int p,int size)
{
  int count=0;
  while(ticket[p]!=0)
  for(int i=0;i<size;i++)
  {
    if(ticket[p]!=0)
    {
      if(ticket[i]>0)
      count++;
      ticket[i]--;
    }
  }
  return count;
}
int main()
{
  int ticket[]={5, 5, 2, 3};
  int p=3;
  int size=sizeof(ticket)/sizeof(ticket[0]);
  cout<<waiting_time(ticket,p,size);
  return 0;
}