n = int(input())
m = []
SIZE = 30001
result = [0] * SIZE
for i in range(n):
    m.append(list(map(int,input().split())))
m.sort(key = lambda x: x[1])
for i in range(n):
    start = m[i][0]
    end = m[i][1]
    fail = 0
    for j in range(start):
        fail = max(fail,result[j])
    result[end] = fail + 1
maxn = 0
for i in range(SIZE):
    maxn = max(maxn, result[i])
print(maxn)

what`s wrong ?

Edited by author 25.11.2022 03:04

Edited by author 25.11.2022 03:04

Hi. I wonder, how can I solve it with dp? I thinked a whole day and cant find the solution less than O(N*T). Give me please some hint.

Use scanline and sort events by right border abd after that just count segments that their l > now so after this make now = r, ans++; firstly ans = 0 and now = 0;
Sorry for my English i'm from Russia

Read tasks and deadlines from the programmer's handbook. similar greedy approach will work in this one.
Also, why is this tagged dp? my dp soln is giving tle

5
1 9
14 15
1 11
12 13
10 15

Right answer is 3, but some algorithmes may give answer 2 for this test.
P.S. I had this mistake:(
P.P.S. Sorry, for my poor English...

if you use dp, l, r can be (>30000).

I still WA on it!!!

If you are using DP, make sure you are using multimap instead of map ( In c++ )

I wrote the following code. It takes 0.748 s, 13 524 KB. Can you suggest something faster?

[code deleted]


Edited by author 01.05.2016 22:19

Edited by moderator 04.12.2019 21:38

#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define ff first
#define ss second
#define maxn 10000009
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
typedef float fl;
typedef vector <int> vint;
typedef vector <vint> vvint;
typedef pair<int,int> pii;
typedef vector<pii> pvint;
typedef vector<bool> bvint;
const int inf=1e9+7;
int n;
int e[30002], dp[30002];
int main(){
    scanf("%d",&n);int ts,te;
    for(int i=1;i<=n;i++) scanf("%d %d",&ts, &te), e[te]=max(e[te], ts);
    for(int i=1;i<=30000;i++)if(e[i]==0) dp[i]=dp[i-1];else dp[i]=max(dp[i],dp[e[i]-1]+1);
    cout << dp[30000];
    return 0;
}

Edited by author 05.04.2017 17:56

Hi, I get tle on test thirteen, but i can't find out what I'm doing wrong. Thank you for helping me!
#include <iostream>
#include <algorithm>
#define DM 100000

using namespace std;

int n, k, m;
pair <int, int> x[DM], a, b;

bool cmp(pair<int,int> a, pair<int,int> b)
{
    if (a.second > b.second)
        return 0;
    return 1;
}

int main()
{
    cin >> n;
    for (; k < n; ++k)
        cin >> x[k].first >> x[k].second;
    sort (x, x + n, cmp);
    k = 1;
    m = x[0].second;
    for (int i = 1; i < n; ++i)
    {
        if (x[i].first > m)
        {
            m = x[i].second;
            ++k;
        }
    }
    cout << k;
    return 0;
}

#include "bits/stdc++.h"
using namespace std;
vector<pair<int,int> > v;
int n;
vector<int> v1;
int dp[100001];
int recurse(int temp){

    if(dp[temp] != -1)
        return dp[temp];

    int search = v[temp].second;
    int lower = lower_bound(v1.begin(), v1.end(), search) - v1.begin();
    // cout << search << " " << lower << "**";
    int max1 = 0;
    for(int i = lower; i < v1.size(); i++){
        // cout << v1[i] << "/" << search << "\n";
        if(v1[i] - search >= 1){
            max1 = max(max1, recurse(i)+1);
        }
    }
    return dp[temp] = max1;
}
int main(int argc, char const *argv[])
{
    // ios::sync_with_stdio(false);
    scanf("%d",&n);
    memset(dp, -1, sizeof dp);
    while(n--){
        int st, en;
        scanf("%d%d",&st,&en);
        v.push_back(make_pair(st, en));
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++){
        v1.push_back(v[i].first);
        // cout << v[i].first << " " << v[i].second << "\n";
    }
    int max1 = 0;
    for(int i  = 0; i < v.size(); i++)
        max1 = max(max1, recurse(i)+1);
    printf("%d",max1);
    return 0;
}

this is my code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    vector <int> A;
    vector <int> B;
    int a,b,n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a>>b;
        A.push_back(a);
        B.push_back(b);
    }
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    a=1;
    b=a;
    for(int i=1; i<n; i++)
    {
    if(A[i]!=A[i-1]) a++;
    if(B[i]!=B[i-1]) b++;
    }
    cout<<min(a,b);
    system("pause");
    return 0;
}

1. Sort it by endTime, if endTime equals another endTime then sort them by startTime.
2. Open one iteration from 2 to n, init just check that,  is endTime<starTime, if so then ans++;
3. print ans; endTime and startTimes is one array with unchanged same index...

Sorry for poor English

This is a famous problem known as "interval scheduling".

My solution in Go (library sort + O(N)) got TLE on 16. Wrote in in C++ and got accepted.
But I really surprised that someone (gadget, zalick, rozdestvenskiy) solved it in Python, which is slower then Go

8
1 2
1 2
3 4
4 5
3 4
1 2
3 4
1 2

Answer 2 p.s. Greedy Algorithm leads to AC

Why my programm does not pass test #7 ?

Give me please that test!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Globalization;
using System.Threading;

namespace _1203.Научная_конференция
{
    class Program
    {
        static void Main(string[] args)
        {
            Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;

            var n = int.Parse(Console.ReadLine().Trim());

            var reports = new List<Tuple<int, int>>(n);
            for(var i = 0; i < n; i++)
            {
                var tokens = Console.ReadLine().Trim().
                    Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
                reports.Add(Tuple.Create(int.Parse(tokens[0]), int.Parse(tokens[1])));
            }

            reports.Sort();

            var weights = new int[n];
            var weight = -1;

            var reportStartComparer = new ReportStartComparer();
            for (var i = 0; i < n; i++)
            {
                if (weights[i] > weight)
                    weight = weights[i];

                var nextReport = Tuple.Create(reports[i].Item2 + 1, 0);
                var idx = reports.BinarySearch(nextReport, reportStartComparer);
                if (idx < 0)
                    idx = ~idx;
                if (idx < n && weights[idx] < weight + 1)
                    weights[idx] = weight + 1;
            }

            Console.WriteLine(weight + 1);
        }
    }

    class ReportStartComparer: IComparer<Tuple<int, int>>
    {
        public int Compare(Tuple<int, int> x, Tuple<int, int> y)
        {
            return x.Item1 - y.Item1;
        }
    }
}

I know AC solution that answers 0 to the following test:
1
29999 30000

Try this:

5
2 3
4 5
6 7
2 8
9 10

The answer is 4.