Touching segments

Question

Can anyone please suggest me algorithm for this.

You are given starting and the ending points of N segments over the x-axis. How many of these segments can be touched, even on their edges, by exactly two lines perpendicular to them?

Sample Input :

3
5
2 3
1 3
1 5
3 4
4 5
5
1 2
1 3
2 3
1 4
1 5
3
1 2
3 4
5 6

Sample Output :

Case 1: 5
Case 2: 5
Case 3: 2

Explanation :

• Case 1: We will draw two lines (parallel to Y-axis) crossing X-axis at point 2 and 4. These two lines will touch all the five segments.
• Case 2: We can touch all the points even with one line crossing X-axis at 2.
• Case 3: It is not possible to touch more than two points in this case.

Constraints:

1 ≤ N ≤ 10^5
0 ≤ a < b ≤ 10^9

Answer 1

Let assume that we have a data structure that supports the following operations efficiently:

1. Add a segment.

2. Delete a segment.

3. Return the maximum number of segments that cover one point(that is, the "best" point).

If have such a structure, we can get use the initial problem efficiently in the following manner:

1. Let's create an array of events(one event for the start of each segment and one for the end) and sort by the x-coordinate.

2. Add all segments to the magical data structure.

3. Iterate over all events and do the following: when a segment start, add one to the number of currently covered segments and remove it from that data structure. When a segment ends, subtract one from the number of currently covered segment and add this segment to the magical data structure. After each event, update the answer with the value of the number of currently covered segments(it shows how many segments are covered by the point which corresponds to the current event) plus the maximum returned by the data structure described above(it shows how we can choose another point in the best possible way).

If this data structure can perform all given operations in O(log n), then we have an O(n log n) solution(we sort the events and make one pass over the sorted array making a constant number of queries to this data structure for each event).

So how can we implement this data structure? Well, a segment tree works fine here. Adding a segment is adding one to a specific range. Removing a segment is subtracting one from all elements in a specific range. Get ting the maximum is just a standard maximum operation on a segment tree. So we need a segment tree that supports two operations: add a constant to a range and get maximum for the entire tree. It can be done in O(log n) time per query.

One more note: a standard segment tree requires coordinates to be small. We may assume that they never exceed 2 * n(if it is not the case, we can compress them).

Answer 2

An O(N*max(logN, M)) solution, where M is the medium segment size, implemented in Common Lisp: touching-segments.lisp.

The idea is to first calculate from left to right at every interesting point the number of segments that would be touched by a line there (open-left-to-right on the lisp code). Cost: O(NlogN)

Then, from right to left it calculates, again at every interesting point P, the best location for a line considering segments fully to the right of P (open-right-to-left on the lisp code). Cost O(N*max(logN, M))

Then it is just a matter of looking for the point where the sum of both values tops. Cost O(N).

The code is barely tested and may contain bugs. Also, I have not bothered to handle edge cases as when the number of segments is zero.