Problem3404--【Div3】区间调度问题 - 课程安排3404: 【Div3】区间调度问题 - 课程安排
[Creator : ]
Time Limit : 1.000 sec Memory Limit : 128 MB
Description
【问题背景】
设想你是学校的教导主任，今天接到任务，有一组课程需要安排，但今天只有一个教室可用。每门课程都有其特定的开始时间和结束时间，你的目标是通过合理的课程安排，使得在这一天内这唯一的教室里能够容纳尽可能多的课程。
【问题描述】
给定一个课程列表，每个课程由一个二元组 (start_time, end_time) 表示，其中 “start_time” 是课程的开始时间，“end_time”是课程的结束时间，且存在不等式0 <= start_time < end_time。时间均为非负整数，代表一天内的某个时刻（例如以小时或分钟为单位，从 0 时刻开始）。
你的任务是设计一个算法，从给定的课程列表中选择出一组互不冲突的课程（即任意两门被选中的课程的时间区间不能有重叠部分，特别规定，一门课程结束的瞬间另一门课程可以立即开始），使得被选中的课程数量达到最多，并输出这个最大数量。
【输入格式】
第一行一个整数n，代表课程总数
接下来n行，每行两个整数，代表一个课程的开始时间和结束时间。
【输出格式】
输出一个整数，表示在不冲突的情况下，这个教室里能够安排的最多课程数量。
【数据范围】
1<=n<=100000