Line Segments

Authored by Adigha on Oct 14 2014

• Problem
• Submissions
• Leaderboard
• Discussions
• Editorial

Problem Statement

You are given N line segments. All of them lie on the same line. We will describe the ith line segment with two integers, Ai and Bi. This means it starts at Ai and ends at Bi. It will be denoted as (Ai;Bi).

Let's say a pair of line segments is good, if one of them is not covering the other one. For example, the pair of (1;4) and (2;5) is good. But the pair of (1;6) and (2;5) is bad because (1;6) covers (2;5).

Let's assume that we have the ith and jth line segments. If Ai≤Aj and Bi≥Bj, we can say "the ith line segment covers jth line segment."

You must find the size of the biggest subset of these line segments that contains no badpairs.

Input Format 
In the first line you are given an integer N, the total number of line segments. 
The next N lines contain two integers, Ai and Bi.

Constraints 
1≤N≤105 
1≤ Ai≤Bi≤109

Output Format 
You must print one integer denoting the size of the biggest subset.

First of all, we must observe that we are trying to choose a subset so the order is not important. If we sort the line segments in ascending order by the start points we just need to compare end points when we need to know a pair of line segments is good or bad. For example if we need to know about i-th line segment and j-th line segment (1≤i≤j≤N) we just need to compare their end points. Because we already know that Ai ≤ Aj. So if Bi ≥ Bj then i-th line segment covers j-th line segment. 

Now if we choose an increasing subsequence (not non-decreasing) from B, this can be the answer subset. Because there will be no bad pairs in that increasing subsequence. 

Few important points 

We sort the vector in ascending order of starting time . howerever when the 

starting time are same we sort the second element according to the decreasing second element. 

suppose the point are 

5

1 9

1 7

1 8

1 6

2 10

the vector sorted should be 

1 1 1 1 2

9 7 8 6 10

and not 

1 1 1 1 2

6 8 7 9 10

Now we find the LIS in the end points. The reason the array was sorted in this

manner was to ensure the points are strictly increasing.

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<vector>

using namespace std;

long long int arr[1000010];

struct sort_pred {

    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {

        if( left.first==right.first)

        return left.second >right.second;

        else

            return left.first <right.first;

    }

};

 int CeilIndex(int A[], int l, int r, int key) {

    int m;

    while( r - l > 1 ) {

        m = l + (r - l)/2;

        (A[m] >= key ? r : l) = m; // ternary expression returns an l-value

    }

    return r;

}

 int LIS(long long int A[], int size) {

    // Add boundary case, when array size is one

    int *tailTable   = new int[size];

    int len; // always points empty slot

    memset(tailTable, 0, sizeof(tailTable[0])*size);

    tailTable[0] = A[0];

    len = 1;

    for( int i = 1; i < size; i++ ) {

        if( A[i] < tailTable[0] )

            // new smallest value

            tailTable[0] = A[i];

        else if( A[i] > tailTable[len-1] )

            // A[i] wants to extend largest subsequence

            tailTable[len++] = A[i];

        else

            // A[i] wants to be current end candidate of an existing subsequence

            // It will replace ceil value in tailTable

            tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i];

    }

    delete[] tailTable;

    return len;

}

int main()

{

     int n;

     cin>>n;

     long long int a,b;

     vector<pair<long long int ,long long int> >v;

     for(int i=0;i<n;i++)

     {

        cin>>a>>b;

v.push_back(make_pair(a,b));  

     }

     sort(v.begin(),v.end(),sort_pred());

     for(int i=0;i<n;i++)

     {

      cout<<v[i].first<<" ";

     }

     for(int i=0;i<n;i++)

     {

      cout<<v[i].second<<" ";

     }

     cout<<endl;

     for(int i=0;i<n;i++)

     {

         arr[i]=v[i].second;

     }

     int ans=LIS(arr,n);

cout<<ans<<endl;

return 0;     

}