目录

题目部分

解读与分析

代码实现

---

题目部分

题目	最小数量线段覆盖
难度	难
题目说明	给定坐标轴（一维坐标轴）上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖住所有线段。
输入描述	第一行输入为所有线段的数量，不超过 10000，后面每行表示一条线段，格式为”x,y"，x 和 y 分别表示起点和终点，取值范围是 [-,]。
输出描述	最少线段数量，为正整数。
补充说明	无
------------------------------------------------------
示例
示例1
输入	3 1,4 2,5 3,6
输出	2
说明	选取 2 条线段 [ 1,4 ] 和 [ 3,6 ]，这两条线段可以覆盖 [ 2,5 ]。

---

解读与分析

题目解读：

在一个一维坐标系中，有很多线段（通过起止点标识），在求出这些线段覆盖的范围之外，求这些线段中至少可以取几个就能覆盖这些范围。

分析与思路：

在解答此题之前，先澄清一下，这些线段覆盖的范围可能是间断的区间。如 3 条线段 [1,4]、[2,5]、[6,7] 覆盖的区间是 [1,5]、[6,7]。

解答此题分三步：排序、分段、回溯。
1. 排序。对所有的线段排序。排序规则为，先对线段的起点进行排序，从小到大；如果起点相等，则对终点排序，也是从小到大。
2. 分段。在前文提到，这些线段覆盖的范围可能是间断的区间。所谓分段，就是找出这些间断的区间。
逐一遍历线段，如果后一个线段的起点大于前一个线段的终点，那么后一个线段就与前一个线段在不同的区间；否则，后一个线段一定与迁移线段处于同一个区间中。
所有位于不同区间的线段绝不会相交，因此，不同分段区间的线段可以单独统计，最后把所有区间的线段之和相加即可。
3. 回溯。对每个单独的区间，使用回溯算法，通过穷举得出所有可能覆盖的情况，从所有的情况中找出所需线段最小的情况。回溯可以使用递归实现，容易理解。

此题时间复杂度为 O()，空间复杂度为 O(n)。

---

代码实现

Java代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;/*** 最少线段覆盖* * @since 2023.09.23* @version 0.1* @author Frank**/
public class MinLineCount {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();int count = Integer.parseInt(input);List<int[]> lines = new ArrayList<>();for (int i = 0; i < count; i++) {input = sc.nextLine();String[] strStartEnd = input.split(",");int[] startEnd = new int[2];startEnd[0] = Integer.parseInt(strStartEnd[0]);startEnd[1] = Integer.parseInt(strStartEnd[1]);lines.add(startEnd);}processMinLineCount( lines);}}private static void processMinLineCount( List<int[]> lines) {// 1. 排序Comparator<int[]> cmp = new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {for (int i = 0; i < o1.length; i++) {if (o1[i] != o2[i]) {return o1[i] - o2[i];}}return 0;}};lines.sort(cmp);// 2. 分段class LinePart {int start; // 起始点，包含在内int end; // 终止点，包含在内int startIdx; // 对应lines中的起始下标，包含在内int endIdx; // 对应lines中的终止下标，包含在内}List<LinePart> lpList = new ArrayList<LinePart>();LinePart tmpLP = new LinePart();for (int i = 0; i < lines.size(); i++) {int[] tmpLine = lines.get(i);if (i == 0) {tmpLP.start = tmpLine[0];tmpLP.end = tmpLine[1];tmpLP.startIdx = 0;tmpLP.endIdx = 0;lpList.add( tmpLP );continue;}// 不是同一个区间if( tmpLine[0] > tmpLP.end ){tmpLP = new LinePart();tmpLP.start = tmpLine[0];tmpLP.end = tmpLine[1];tmpLP.startIdx = i;tmpLP.endIdx = i;lpList.add( tmpLP );continue;}else  // 同一个区间{tmpLP.end = tmpLine[1];tmpLP.endIdx = i;}}//3.逐段求和int count = 0;for( int i = 0; i < lpList.size(); i ++ ){LinePart lpPart = lpList.get( i );List<int[]> tmpList = new ArrayList<int[]>();for( int j = lpPart.startIdx; j <= lpPart.endIdx; j ++ )	//  j <= lpPart.endIdx，包含在内{int[] tmpLine = lines.get( j );int[] copy = new int[2];copy[0] = tmpLine[0];copy[1] = tmpLine[1];tmpList.add( copy );}int partCount = getPartMinCount( tmpLP.start, tmpLP.end, tmpList );count += partCount;}System.out.println( count );}private static int getPartMinCount( int start, int end, List<int[]> list){if( start >= end ){return 0;}int minCount = list.size();for( int i = 0; i < list.size(); i ++ ){int tmpCount = 0;int[] cur = list.get( i );// 当它已经无法覆盖if( cur[0] > start ){break;}// 如果end小于start，那这样的线段根本不需要if( cur[1] < start  ){continue;}list.remove( i );tmpCount ++;tmpCount += getPartMinCount( cur[1], end, list);list.add( i, cur );if( tmpCount < minCount ){minCount = tmpCount;}}return minCount;}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var count = parseInt(line);var lines = new Array();for (var i = 0; i < count; i++) {line = await readline();var strStartEnd = line.split(",");var startEnd = [];startEnd[0] = parseInt(strStartEnd[0]);startEnd[1] = parseInt(strStartEnd[1]);lines[i] = startEnd;}processMinLineCount(lines);}
}();function compareLineFun(a, b) {for (var i = 0; i < a.length; i++) {if (a[i] != b[i]) {return a[i] - b[i];}}return 0;
}function processMinLineCount(lines) {// 1. 排序lines.sort(compareLineFun);// 2. 分段// LinePart 的数据结构// LinePart  {//      start; // 起始点，包含在内//      end; // 终止点，包含在内//      startIdx; // 对应lines中的起始下标，包含在内//      endIdx; // 对应lines中的终止下标，包含在内//  }var lpList = new Array();var tmpLP = {};for (var i = 0; i < lines.length; i++) {var tmpLine = lines[i];if (i == 0) {tmpLP.start = tmpLine[0];tmpLP.end = tmpLine[1];tmpLP.startIdx = 0;tmpLP.endIdx = 0;lpList.push(tmpLP);continue;}// 不是同一个区间if (tmpLine[0] > tmpLP.end) {tmpLP = new LinePart();tmpLP.start = tmpLine[0];tmpLP.end = tmpLine[1];tmpLP.startIdx = i;tmpLP.endIdx = i;lpList.push(tmpLP);continue;} else // 同一个区间{tmpLP.end = tmpLine[1];tmpLP.endIdx = i;}}//3.逐段求和var count = 0;for (var i = 0; i < lpList.length; i++) {var lpPart = lpList[i];var tmpList = new Array();for (var j = lpPart.startIdx; j <= lpPart.endIdx; j++) //  j <= lpPart.endIdx，包含在内{var tmpLine = lines[j];var copy = [];copy[0] = tmpLine[0];copy[1] = tmpLine[1];tmpList.push(copy);}var partCount = getPartMinCount(tmpLP.start, tmpLP.end, tmpList);count += partCount;}console.log(count);
}function getPartMinCount(start, end, list) {if (start >= end) {return 0;}var minCount = list.length;for (var i = 0; i < list.length; i++) {var tmpCount = 0;var cur = list[i];// 当它已经无法覆盖if (cur[0] > start) {break;}// 如果end小于start，那这样的线段根本不需要if (cur[1] < start) {continue;}list.splice(i, 1);tmpCount++;tmpCount += getPartMinCount(cur[1], end, list);list.splice(i, 0, cur);if (tmpCount < minCount) {minCount = tmpCount;}}return minCount;
}

此题难度有些大，从思考算法，到实现代码并通过测试，都有不少工作量。在华为 OD 考题中，属于难度较大的题。

(完)