You are not logged in. Please login at to post your questions!


Need an efficient algorithm to solve the following problem

The problem is the following:

Given N containers with different sizes between 1 and N (2 <= N <= 10^5), each of them placed in a line, determine how many places can be freed if one container can be placed in another only if its size is less that the others size and they don't have any other containers between them. Multiple placings can be made, so if there are containers placed in each other, they can be placed in another container (if the bottom container size is less than the others size), a container can be placed in another group of container (if its size is less than the top container size), and a group of containers can be placed in another group of containers with similar rules. Example: if N = 8 and the containers are placed in the following order: 1 8 2 4 3 6 7 5, then 7 places can be freed; we place 3 in 4, then 2 in 3, 6 in 7, 5 in 6, 4 in 5, 7 in 8, and 1 in 2. This way all the containers can be packed in a single group.

My idea of solving this problem is the following: calculate the minimum difference between all the neighbour containers sizes, then find the first pair where this minimum appears and make a placement. Then repeat the whole process again until no placements can be made. Then calculate the freed places. This can be done trivially in quadratic time, but that is too slow. The other thing that bothers me that this method may not lead to the optimal solution.

Note: I have to implement the algorithm in C++, and my program has to finish in 200ms. This is why a quadratic solution has no chance. Also, I don't want to have my job done by others, I posted this because I got stuck solving the problem, and needed some help to know if my approach is correct or how can I make optimizations.

asked 16 Feb, 16:54

kkriszel's gravatar image

accept rate: 0%

which size container occurs the most number of times? How many times? Just print this no.


answered 16 Feb, 17:22

galavk's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 16 Feb, 16:54

question was seen: 76 times

last updated: 16 Feb, 17:22