Answer the question
In order to leave comments, you need to log in
Algorithm for assigning the neighbor's apartment number from below for several apartments at once
Let's say there is a house, one apartment per floor, 9 floors. Let's say that the apartment number (N) will also be the apartment ID and the number is unchanged, while the apartment number can change, that is,
N | ID
9 | 9
8 | 8
7 | 7
6 | 6
5 | 5
4 | 4
3 | 3
2 | 2
1 | 1
Suppose we need to combine several apartments in pairs with neighbors from below and at the same time maintain the correct numbering. Let's say for apartments with ID 3 and 5, we get
N | ID
7 | 9
6 | 8
5 | 7
4 | 6
3 | 5
3 | 4
2 | 3
2 | 2
1 | 1
So far I have come up with one solution:
1. find the apartment number from below
2. update the apartment number above
3. all apartment numbers above the ID is N = N-1
and so on for each changed ID
Can someone else suggest a more optimal algorithm?
Answer the question
In order to leave comments, you need to log in
From the example you provided, you can see that the apartment number is equal to the ID minus the number of IDs to change that are less than or equal to the current one.
Those.
N(2) = 2 - 0 = 2
N(3) = 3 - |{3}| = 2
N(4) = 4 - |{3}| = 3
N(5) = 5 - |{3, 5}| = 3
i.e. for each request for a number - the complexity of the answer will be O (m), where m is the number of IDs to be changed (it can be faster).
If there are a lot of requests, then it is better to update everything at once. For example:
Let's regenerate all numbers starting from the first one so that the number of the next apartment is equal to the value of the counter. The counter value is incremented only if the current ID is not equal to one of the mutable ones. Otherwise, the counter is not incremented.
The final complexity is O(n) provided that ID membership is checked for O(1).
To be honest, I tried to understand the essence of the problem for a very long time. The solution seems too simple. Perhaps I misunderstood something.
Instead of an array, you can use a segment tree. Then finding/updating the number by id will be done in O(log(n)), reducing the entire tail by 1 in O(log(n)), finding id by number in O(log(n)^2) (via binary search ). Instead of a segment tree, you can use a set of united apartments - there will be the same asymptotics, but then the set must support the operation “How many elements are to the left of this one”
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question