您好,登錄后才能下訂單哦!
這篇文章主要為大家展示了“Java中算法提高之線段和點(diǎn)的示例分析”,內(nèi)容簡(jiǎn)而易懂,條理清晰,希望能夠幫助大家解決疑惑,下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“Java中算法提高之線段和點(diǎn)的示例分析”這篇文章吧。
1.0s 內(nèi)存限制:256.0MB
有n個(gè)點(diǎn)和m個(gè)區(qū)間,點(diǎn)和區(qū)間的端點(diǎn)全部是整數(shù),對(duì)于點(diǎn)a和區(qū)間[b,c],若a>=b且a<=c,稱點(diǎn)a滿足區(qū)間[b,c]。
求最小的點(diǎn)的子集,使得所有區(qū)間都被滿足。
第一行兩個(gè)整數(shù)n m
以下n行 每行一個(gè)整數(shù),代表點(diǎn)的坐標(biāo)
以下m行 每行兩個(gè)整數(shù),代表區(qū)間的范圍
輸出一行,最少的滿足所有區(qū)間的點(diǎn)數(shù),如無解輸出-1。
樣例輸入:
5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9
樣例輸出:
2
1<=n,m<=10000
0<=點(diǎn)和區(qū)間的坐標(biāo)<=50000
import java.io.IOException; import java.io.InputStream; import java.util.Arrays; import java.util.Comparator; public class xianduanhedian { private static InputStream is = System.in; public static int nextInt() { try { int i; while ((i = is.read()) < 45 || i > 57) { } int mark = 1, temp = 0; if (i == 45) { mark = -1; i = is.read(); } while (i > 47 && i < 58) { temp = temp * 10 + i - 48; i = is.read(); } return temp * mark; } catch (IOException e) { e.printStackTrace(); } return -1; } static class Node { public int start; public int end; public Node(int start, int end) { this.start = start; this.end = end; } } public static void main(String[] args) { int n = nextInt(); int m = nextInt(); int point[] = new int[n]; for (int i = 0; i < n; i++) point[i] = nextInt(); Node node[] = new Node[m]; for (int i = 0; i < m; i++) node[i] = new Node(nextInt(), nextInt()); Arrays.sort(point); Arrays.sort(node, new Comparator<Node>() { public int compare(Node o1, Node o2) { return o1.end - o2.end; } }); int currentPoint = 0; int count = 0; int j = 1; for (int i = 0; i < m; i++) { int x = node[i].start; int y = node[i].end; if (x <= currentPoint) continue; int temp = -1; for (j -= 1; j < n; j++) { if (point[j] <= y) { temp = point[j]; } else { break; } } if (temp == -1) { count = 0; break; } else { currentPoint = temp; count++; } } System.out.println(count); } }
以上是“Java中算法提高之線段和點(diǎn)的示例分析”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。