Fitting a segment in a two-dimensional plane

Question

I'm having troubles with the following problem

Given N x S grid and m segments parallel to the horizontal axis (all of them are tuples (x', x'', y)), answer Q online queries of form (x', x''). The answer to such a query is the smallest y (if there is one) such that we can place a segment (x', x'', y). All segments are non-overlapping yet beginning of one segment can be the ending of another i.e. segments (x', x'', y) and (x'', x''', y) are allowed. Being able to place a segment means there could exist a segment (x', x'', y) that wouldn't violate stated rules, segment isn't actually placed(board with initial segments isn't modified) but we only state there could be one.

Constraints

1 ≤ Q, S, m ≤ 10^5
1 ≤ N ≤ 10^9

Time: 1s
Memory: 256 Mb

Here is an example from the link below. Input segments are (2, 5, 1), (1, 2, 2), (4, 5, 2), (2, 3, 3), (3, 4, 3).
Answer for queries

1) (1, 2) → 1

2) (2, 3) → 2

3) (3, 4) → 2

4) (4, 5) → 3

5) (1, 3) → can't place a segment

A visualized answer for the third query (blue segment):

I don't quite understand how to approach the problem. It is supposed to be solved with persistent segment tree, but I am still unable to come up with something.

Could you help me please.

This is not my homework. The source problem can be found here http://informatics.mccme.ru/mod/statements/view3.php?chapterid=111614 . There's no English version of the statement avaliable and the test case presents input data in a different way, so don't mind the souce.

Hosey

I don't get why the answer to the query (2, 3) would be 2? Where could a segment (2, 3, 2) be placed? – Tinsmith

@Tinsmith As the beginning of one segment can be the end of another there is nothing wrong with a segment (2, 3, 2), it would 'extend' segment (1, 2, 2), making them look like a single segment (1, 3, 2) (thought the segment is just hypothetical as initial board doesn't change) – Hosey

Maybe you add a little drawing to illustrate an example? – Tinsmith

The problem statement says the queries are online - look at the formula a  =  x_i  + p , b  =  y_i  +  p , and how p updates. If we are given all queries beforehand, the problem is much easier. – Contestation

Answer 1

Here is an O(N log N) time solution.

Preliminaries (a good tutorial available here): segment tree, persistent segment tree.

Part 0. Original problem statement

I briefly describe the original problem statement as later I'm going to speak in its terms rather than in terms of abstract segments.

There is a train with S seats (S <= 10^5). It is known that seat s_i is occupied from time l_i to time r_i (no more than 10^5 such constraints, or passengers). Then we have to answer 10^5 queries of kind "find the lowest number of a seat with is free from time l_i to time r_i or say if there is none". All queries must be answered online, that is, you have to answer the previous query before seeing the next.

Throughout the text I denote with N both the number of seats, the number of passengers, and the number of queries, assuming they are the same order of magnitude. You can do more accurate analysis if needed.

Part 1. Answering a single query

Let's answer a query [L, R] assuming that there are no occupied places after time R. For each seat we maintain the last time when it is occupied. Call it last(S). Now the answer for the query is minimum S such that last(S) <= L. If we build a segment tree on seats then we'll be able to answer this query in O(log^2 N) time: binary search the value of S, check if range minimum on segment [0, S] is at most L.

However, it might be not enough to get Accepted. We need O(log N). Recall that each node of a segment tree stores minimum in corresponding range. We start at the root. If the minimum there is >= L then there is no available seat for such query. Otherwise either minimum in the left child or in the right child is <= L (or in both). In the first case we descend to the left child, in the second – to the right, and repeat until we reach a leaf. This leaf will correspond to the minimum seat with last(S) <= L.

Part 2. Solving the problem

We maintain a persistent tree on seats, storing last(S) for each seat (same as in the previous part). Let's process initial passengers one by one sorted by their left endpoint in increasing order. For a passenger (s_i, l_i, r_i) we update the segment tree at position s_i with value r_i. The tree is persistent, so we store the new copy somewhere.

To answer a query [L, R], find a latest version of the segment tree such that the update happened before R. If you do a binary search on versions, it takes O(log N) time.

In the version of the segment tree only passengers with their left endpoint < R are considered (even more, exactly such passengers are). So we can use the algorithm from the Part 1 to answer the query using this segment tree.

Khania

Answer 2

Statement :

Input : list<x',x'',Y>

Query Input : (X',X'')

Output : Ymin

Constraints :

1 ≤ Q, S, m ≤ 10^5
1 ≤ N ≤ 10^9

Time: 1s
Memory: 256 Mb

---

Answer:

Data structure method you can use :

1. Brute force : Directly iterate through the list and perform the check.

---

2. Sort : sort the list on Y [lowest to highest] and then iterate through it.

Note : Sorting large list will be time consuming.

Sort on Y
Ymin = -1                                            //Maintain Ymin
for i[0 : len(input)] :                              //Iterate through tuples
    if Ymin != -1 && Y(i-1) != Yi : return Ymin      // end case
    else if x' > X'' : Ymin = Yi                     //its on right of query tuple
    else if x'<X' && (x' + length <= X') : Ymin = Yi //on left of query tuple
    else next

---

3. Hashmap : Map<Y, list< tuple<x',length> > > to store list of lines for each Y and iterate through them to get least Y.

Note : will take additional time for Map build.

Iterate through list and build a Map 
Iterate through Map keys :
    Iterate through list of tuples, for each tuple :
        if x' > X'': Continue                            //its on right of query tuple
        else if x'<X' && (x' + length <= X') :  return Y //on left of query tuple
            else next Y

---

4. Matrix : you can build matrix with 1 for occupied point and 0 for empty.

Note : will take additional time for Matrix build and iteration through matrix is time consuming so not useful.

Example :

    0 1 1 1 0 0 
    1 1 0 1 0 0
    0 1 1 1 1 0

Carmacarmack