题目描述
给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。
输入描述
第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”,
x和y 分别表示起点和终点,取值范围是[-10^5 ,10^5]。
输出描述最少线段数量,为正整数。
输入
3
1,4
2,5
3,6
输出
2
题意解读
首先,用示例来理解题意:现在有三条线段:
一号线段:起点1,终点4;
二号线段:起点2,终点5;
三号线段:起点3,终点6;
我们要从这三条线段中,选出若干条线段,覆盖1~6
整个区间。
比如,我们可以选择 一号、二号、三号。一号覆盖 1~4
,二号覆盖 2~5
,三号覆盖3~6
,三条线段加起来可以覆盖1~6</