インターバルスケジューリング問題の貪欲な解決策（java）

Greedy Solution Interval Scheduling Problem

問題の説明：

n個のジョブがあり、各ジョブはsi時間に開始し、ti時間に終了します。ジョブごとに、参加するかどうかを選択できます。参加する場合は、最初から最後までのプロセス全体に参加する必要があります。さらに、作業セグメントに参加する時間を繰り返すことはできません（開始と終了の瞬間の重複も許可されていません）。あなたの目標はできるだけ多くの仕事に参加することですが、最大でいくつのタスクに参加できますか？
1≤n≤100000
1≤si≤ti≤10^ 9
入力：
最初の行：n
2行目：n個の整数スペースで区切られ、n個のジョブの開始時刻を表します
3行目：n個の整数スペースで区切られ、n個のジョブの終了時刻を表します
サンプル入力：
5
1 2 4 6 8
3 5 7 9 10
サンプル出力：
3
説明：ジョブ1、3、5を選択します
アイデア分析：

強引な方法と比較して、欲張りアルゴリズムは速度を大幅に改善し、時間の複雑さは無視されます。各ジョブの開始時刻と終了時刻をパックする、つまりクラスに入れて、終了時刻のサイズに従って並べ替えることができます（終了時刻が早いほど、他の作業にかかる時間が長くなります）。これにより、ジョブの数が増加します）。

特にコードコメントを参照してください。

import java.util.Arrays import java.util.Scanner public class Qjdut { //Interval scheduling (greedy calculation) private static class time implements Comparable{ private int st//start time private int et//end time public time(int a,int b)//Constructor { this.et=a this.st=b } @Override //If you want to use sort for sorting, you must rewrite the compareto function public int compareTo(time o) { int x=this.et-o.et if (x==0) { int y=this.st-o.st if (y==0) return 0 else if (y0) return 1 else return -1 } } public static int solve(time[] times) { int cnt=1//Number of records int tet=times[0].et//Record the first earliest end time for (int i=1itet)//Satisfy the conditions, count plus one { cnt++ tet=times[i].et//Update the end value } } return cnt } public static void main(String[] args) { Scanner a=new Scanner(System.in) int n=a.nextInt()//number int []start=new int[n]//start time int []end=new int[n]//End time for (int i=0i

操作効果は以下のとおりです。