一个新的网站开发语言,服装网站建设策划,深圳建筑业协会官网,网站开发要学多久Problem: AcWing 803. 区间合并 文章目录 思路解题方法复杂度Code 思路 这是一个区间合并的问题。我们需要找出尽可能多的不相交的区间。首先#xff0c;我们将所有的区间按照左端点从小到大进行排序。然后#xff0c;我们遍历所有的区间#xff0c;如果当前区间的左端点大于… Problem: AcWing 803. 区间合并 文章目录 思路解题方法复杂度Code 思路 这是一个区间合并的问题。我们需要找出尽可能多的不相交的区间。首先我们将所有的区间按照左端点从小到大进行排序。然后我们遍历所有的区间如果当前区间的左端点大于上一个区间的右端点那么我们就可以选择这个区间否则我们就跳过这个区间。 解题方法 我们使用一个变量 r 来记录上一个选择的区间的右端点。初始时r 是最小的整数。我们遍历所有的区间如果当前区间的左端点大于 r那么我们就选择这个区间并更新 r 为当前区间的右端点。最后我们输出选择的区间的数量。 复杂度
时间复杂度: O ( n l o g n ) O(n log n) O(nlogn)其中 n n n 是区间的数量。我们需要对所有的区间进行排序排序的时间复杂度是 O ( n l o g n ) O(n log n) O(nlogn)。 空间复杂度: O ( n ) O(n) O(n)其中 n n n 是区间的数量。我们需要用一个列表来存储所有的区间。 Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int n;static Listint[] list new ArrayList();public static void main(String[] args) throws IOException {n nextInt();for (int i 0, l, r; i n; i) {l nextInt();r nextInt();list.add(new int[] { l, r });}Collections.sort(list, new Comparatorint[]() {public int compare(int[] o1, int[] o2) {// TODO Auto-generated method stubreturn o1[0] - o2[0];}});int ans 0;int r Integer.MIN_VALUE;for (int[] arr : list) {if(arr[0] r) {ans;}r Math.max(r, arr[1]);}out.println(ans);out.flush();}private static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
