动态规划和贪心思想结合求解

解题思路:首先先处理输入的n组活动，建立一个数组存储以索引代表开始时间，数组的值为结束时间，适当选择数组长度，比如a[1]=3，就是代表开始时间为1，结束时间为3的一个活动，也许有人会想不止一个活动开始时间为1的活动，的确是这样，但是我们只需要结束时间最早但开始时间为1的活动，因为能容下开始时间相同但结束时间大的那就肯定能容下结束时间早的，反正只要考虑容纳数，所以在输入的过程中将同一开始时间但是最早结束的活动时间保存至数组中，再建立一个二维数组dp[2001][2001]，按照状态转移方程遍历一遍即可，二维数组第一个索引  i  的意思代表可以使用开始时间小于 i 的活动，第二个索引  j  的值代表最大结束时间不超过j，最后在遍历过程中，找到最大值即可求出最大容纳活动数
注意事项: 

根据数据规模调整dp数组的长度
参考代码:

import java.util.Scanner;

public class Main {

    static Scanner sc1=new Scanner(System.in);

    public static void main(String[] args) {

        int N=sc1.nextInt();

        int[] sz=new int[2001];

        for(int i=0;i<2001;i++) {

        sz[i]=999999;//方便输入过程中比较存储较小的值

        }

        for(int i=0;i<N;i++) {

        int a1=sc1.nextInt(),a2=sc1.nextInt();

        if(sz[a1]>a2)sz[a1]=a2;//通过比较记录最早结束但开始时间相同的活动

        }

        int ans=0;//保存dp数组最大值，即为结果

        int dpsz[][]=new int[2001][2001];

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

        int j=1;

        for(;j<2001;j++){

        if(j<sz[i])//    状态转移方程

        dpsz[i][j]=dpsz[i-1][j];

        else//   状态转移方程

        dpsz[i][j]=dpsz[i][i]+1;

        if(ans<dpsz[i][j])

                    ans=dpsz[i][j];//遍历过程中保留最大值，即为最大容纳数

        }

        }

        System.out.println(ans);

    }

}