Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- #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;
- }
- $ 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
- $
- 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));
- }
- }
- def incr_i n, i
- i += 1
- i = 0 if i >= n
- i
- end
- def waitingTime(tickets, p)
- time = 0
- i = 0
- n = tickets.size
- # Note: a timeout can be added for avoiding infinite loops
- while true
- next i = incr_i(n, i) if tickets[i] <= 0
- #puts "#{tickets.to_s}, i: #{i}, time: #{time}"
- tickets[i] -= 1
- time += 1
- break if tickets[p] <= 0
- i = incr_i(n, i)
- end
- time
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement