Advertisement
Guest User

Untitled

a guest
Jul 19th, 2017
495
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.00 KB | None | 0 0
  1. long waitingTime(vector<int> tickets, int p) {
  2. // bool flag indicates whether it's Jesse or not
  3. queue<pair<int, bool> > aQueue;
  4.  
  5. for(int i = 0; i < tickets.size(); i++) {
  6. aQueue.push(make_pair(tickets[i], i == p));
  7. }
  8.  
  9. long long nTime = 1;
  10. while(!aQueue.empty()) {
  11. pair<int, bool> aItem = aQueue.front();
  12. aQueue.pop();
  13. nTime++;
  14. if(aItem.first == 1 && aItem.second == true)
  15. break;
  16. else if(aItem.first > 1) {
  17. aQueue.push(make_pair(aItem.first-1, aItem.second));
  18. }
  19. }
  20. return nTime-1;
  21. }
  22.  
  23. #include <algorithm>
  24. #include <iostream>
  25. #include <queue>
  26. #include <vector>
  27.  
  28. // naive approach
  29.  
  30. int waitingTimeSim(const std::vector<int> &tickets, int p)
  31. {
  32. // setup sim. model
  33. std::queue<std::pair<int, bool> > people;
  34. for (int i = 0, n = (int)tickets.size(); i < n; ++i) {
  35. people.push(std::make_pair(tickets[i], i == p));
  36. }
  37. // simulation
  38. int tP = 0;
  39. for (;;) {
  40. std::pair<int, bool> person = people.front();
  41. people.pop();
  42. --person.first; ++tP; // buy ticket
  43. if (!person.first) { // if person is done
  44. if (person.second) return tP; // It's Jesse -> terminate
  45. } else people.push(person);
  46. }
  47. }
  48.  
  49. // analytical approach
  50.  
  51. int waitingTime(const std::vector<int> &tickets, int p)
  52. {
  53. int tP = 0, ticketsP = tickets[p];
  54. for (int i = 0, n = (int)tickets.size(); i < n; ++i) {
  55. tP += std::min(tickets[i], ticketsP - (i > p));
  56. // i > p -> people after jesse -> decr. by 1
  57. }
  58. return tP;
  59. }
  60.  
  61. int main()
  62. {
  63. { std::vector<int> tickets{ 2, 6, 3, 4, 5 };
  64. for (int p = 0, n = tickets.size(); p < n; ++p) {
  65. std::cout << "tickets{ 2, 6, 3, 4, 5 }, p = " << p << std::endl;
  66. int tS = waitingTimeSim(tickets, p);
  67. std::cout << "simulated t: " << tS << std::endl;
  68. int t = waitingTime(tickets, p);
  69. std::cout << "computed t: " << t << std::endl;
  70. }
  71. }
  72. { std::vector<int> tickets{ 5, 5, 2, 3 };
  73. for (int p = 0, n = tickets.size(); p < n; ++p) {
  74. std::cout << "tickets{ 5, 5, 2, 3 }, p = " << p << std::endl;
  75. int tS = waitingTimeSim(tickets, p);
  76. std::cout << "simulated t: " << tS << std::endl;
  77. int t = waitingTime(tickets, p);
  78. std::cout << "computed t: " << t << std::endl;
  79. }
  80. }
  81. return 0;
  82. }
  83.  
  84. $ g++ -std=c++11 -o waiting-queue waiting-queue.cc
  85.  
  86. $ ./waiting-queue.exe
  87. tickets{ 2, 6, 3, 4, 5 }, p = 0
  88. simulated t: 6
  89. computed t: 6
  90. tickets{ 2, 6, 3, 4, 5 }, p = 1
  91. simulated t: 20
  92. computed t: 20
  93. tickets{ 2, 6, 3, 4, 5 }, p = 2
  94. simulated t: 12
  95. computed t: 12
  96. tickets{ 2, 6, 3, 4, 5 }, p = 3
  97. simulated t: 16
  98. computed t: 16
  99. tickets{ 2, 6, 3, 4, 5 }, p = 4
  100. simulated t: 19
  101. computed t: 19
  102. tickets{ 5, 5, 2, 3 }, p = 0
  103. simulated t: 14
  104. computed t: 14
  105. tickets{ 5, 5, 2, 3 }, p = 1
  106. simulated t: 15
  107. computed t: 15
  108. tickets{ 5, 5, 2, 3 }, p = 2
  109. simulated t: 7
  110. computed t: 7
  111. tickets{ 5, 5, 2, 3 }, p = 3
  112. simulated t: 11
  113. computed t: 11
  114.  
  115. $
  116.  
  117. import java.util.Arrays;
  118. import java.util.List;
  119.  
  120. public class TickerPurcahseTime {
  121. public static int calculateTimeOptimized(List<Integer> line, int pos) {
  122. // Minimum time I have to wait is the number of tickets I want to buy.
  123. int waitingTime = line.get(pos);
  124. for (int i = 0; i < line.size(); i++) {
  125. if (i == pos) continue;
  126. // I will see people -> minimum(how many tickets I need, how many tickets they need).
  127. waitingTime += (Math.min(line.get(pos), line.get(i)));
  128. // Unless they were behind me, I got my ticket before them so I need to see them 1 time less.
  129. if (i > pos) {
  130. waitingTime--;
  131. }
  132. }
  133.  
  134. return waitingTime;
  135. }
  136.  
  137. public static void main(String [] args) {
  138. System.out.println(calculateTimeOptimized(Arrays.asList(5, 5, 2, 3), 3));
  139. }
  140. }
  141.  
  142. def incr_i n, i
  143. i += 1
  144. i = 0 if i >= n
  145. i
  146. end
  147.  
  148. def waitingTime(tickets, p)
  149. time = 0
  150. i = 0
  151. n = tickets.size
  152. # Note: a timeout can be added for avoiding infinite loops
  153. while true
  154. next i = incr_i(n, i) if tickets[i] <= 0
  155. #puts "#{tickets.to_s}, i: #{i}, time: #{time}"
  156. tickets[i] -= 1
  157. time += 1
  158. break if tickets[p] <= 0
  159. i = incr_i(n, i)
  160. end
  161.  
  162. time
  163. end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement