题解 | #活动安排#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.valueOf(scan.nextLine().trim());
        int[][] activities = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] strs = scan.nextLine().split(" ");
            activities[i][0] = Integer.valueOf(strs[0]);
            activities[i][1] = Integer.valueOf(strs[1]);
        }
        mergeSort(activities);
        int ans = 1;
        int endTime = activities[0][1];
        for (int i = 1; i < activities.length; i++) {
            if (activities[i][0] >= endTime) {
                ans++;
                endTime = activities[i][1];
            }
        }
        System.out.println(ans);
    }
    public static void mergeSort(int[][] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        process(nums, 0, nums.length - 1);
    }
    public static void process(int[][] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + ((end - start) >> 1);
        process(nums, start, mid);
        process(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }
    public static void merge(int[][] nums, int start, int mid, int end) {
        int[][] helper = new int[end - start + 1][2];
        int index = 0;
        int p1 = start;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= end) {
            if (nums[p1][1] < nums[p2][1]) {
                helper[index][0] = nums[p1][0];
                helper[index][1] = nums[p1][1];
                index++;
                p1++;
            } else if (nums[p1][1] > nums[p2][1]) {
                helper[index][0] = nums[p2][0];
                helper[index][1] = nums[p2][1];
                index++;
                p2++;
            } else {
                if (nums[p1][0] <= nums[p2][0]) {
                    helper[index][0] = nums[p1][0];
                    helper[index][1] = nums[p1][1];
                    index++;
                    p1++;
                } else {
                    helper[index][0] = nums[p2][0];
                    helper[index][1] = nums[p2][1];
                    index++;
                    p2++;
                }
            }
        }
        while (p1 <= mid) {
            helper[index][0] = nums[p1][0];
            helper[index][1] = nums[p1][1];
            index++;
            p1++;
        }
        while (p2 <= end) {
            helper[index][0] = nums[p2][0];
            helper[index][1] = nums[p2][1];
            index++;
            p2++;
        }
        for (int i = 0; i < helper.length; i++) {
            nums[start + i][0] = helper[i][0];
            nums[start + i][1] = helper[i][1];
        }
    }
}