系列文章目錄

---

前言

本人最近再練習算法，所以會發布一些解題思路，希望大家多指教

一、題目描述

給定坐標軸上的一組線段，線段的起點和終點均為整數并且長度不小于1，請你從中找到最少數量的線段，這些線段可以覆蓋住所有線段。

二、輸入描述

第一行輸入為所有線段的數量，不超過10000，后面每行表示一條線段，格式為"x,y"，x和y分別表示起點和終點，取值范圍是[-105,105]。

三、輸出描述

最少線段數量，為正整數。

四、java代碼

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = Integer.parseInt(sc.nextLine());List<int[]> list = new ArrayList<>();for (int i = 0; i < N; i++) {String[] split = sc.nextLine().split(" ");list.add(new int[]{Integer.parseInt(split[0]), Integer.parseInt(split[1])});}//按照線段的左側下標進行正序排序，相同時，按照右側下標正序排序list.sort(((o1, o2) -> {if (o1[0]==o2[0]) {return o1[1] - o2[1];} else {return o1[0] - o2[0];}}));//初始化線段數量，默認都無法完成覆蓋int num = list.size();for (int i = 0; i < list.size(); i++) {int[] ints = list.get(i);if(i+1 <list.size()){//情況一：如果兩個線段左側下標相同，因為前面已經進行排序，所以后面的一定可以覆蓋當前線段if(ints[0] == list.get(i+1)[0]){num--;} else if(ints[1] >= list.get(i+1)[1]){//情況二：如果右側下標相同，則當前線段的一定可以覆蓋下一個線段num--;//將下一個覆蓋的線段的右側下標進行延伸，繼續向后比較list.get(i+1)[1] = ints[1];}}}System.out.println(num);}

五、測試用例

輸入：
6
15 20
3 6
8 12
1 7
11 15
18 20