Saturday, 16 Oct 2021

# Maximize count of intersecting line segments

Given two arrays X[] and Y[], representing points on X and Y number lines, such that every similar-indexed array element forms a line segment, i.e. X[i] and Y[i] forms a line segment, the task is to find the maximum number of line segments that can be selected from the given array.
Examples:

Input: X[] = {0, 3, 4, 1, 2}, Y[] = {3, 2, 0, 1, 4}Output: 3Explanation: The set of line segments are {{1, 1}, {4, 0}, {0, 3}}.
Input: X[] = {1, 2, 0}, Y[] = {2, 0, 1}Output: 2Explanation: The set of line segments is {{1, 2}, {2, 0}}.

Approach: The problem can be solved using the observation that the intersection between two line-segments (i, j) occurs only when X[i] < X[j] and Y[i] > Y[j] or vice-versa. Therefore, the problem can be solved using Sorting along with Binary search, using Sets can be used to find such line segments.Follow the steps below to solve the given problem:
Initialize a vector of pairs, say p to store pairs {X[i], Y[i]} as an element.
Sort the vector of pairs p in ascending order of points on X number line, so every line segment i satisfies the first condition for the intersection i.e X[k] < X[i] where k < i. Initialize a Set, say s, to store the values of Y[i] in descending order. From the first element from p, push the Y-coordinate (i.e p.second) into the set. Iterate over all the elements of p, and for each element: Perform a binary search to find the lower_bound of p[i].second. If there is no lower bound obtained, that means that p[i].second is smaller than all the elements present in the Set. This satisfies the second condition that Y[i] < Y[k] where k < i, so push p[i].second into the Set. If a lower bound is found, then remove it and push p[i].second into the Set. Finally, return the size of the set that as the result. Below is the implementation of the above approach: C++ #include using namespace std;    int solve(int N, int X[], int Y[]) {               vector p;        for (int i = 0; i < N; i++) {                  p.push_back({ X[i], Y[i] });     }                  sort(p.begin(), p.end());                  set s;             s.insert(p.second);        for (int i = 0; i < N; i++) {                              auto it = s.lower_bound(p[i].second);                     if (it == s.end()) {                             s.insert(p[i].second);         }         else {                                          s.erase(*it);                                          s.insert(p[i].second);         }     }                  return s.size(); }    int main() {          int N = 5;     int X[] = { 1, 2, 0 };     int Y[] = { 2, 0, 1 };                  int maxintersection = solve(N, X, Y);     cout