区间合并（c++,java)
给定一个长度为 n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n个整数（均在 0∼105范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例：
5
1 2 2 3 5
输出样例：
3
提交代码
c++
#include<bits/stdc++.h> using namespace std; typedef pair<int, int> PII; vector<PII> segs; void merge(vector<PII> &s) { int st = -2e9, ed = -2e9; vector<PII> res; for (auto item:s) { if (ed < item.first) { res.push_back({st, ed}); st = item.first, ed = item.second; } else ed = max(ed, item.second); } segs = res; } int main() { int n; cin >> n; while(n --) { int l, r; cin >> l >> r; segs.push_back({l, r}); } sort(segs.begin(), segs.end()); merge(segs); cout << segs.size() << endl; return 0; }
java
import java.util.*; public class Main { static int N = 100010; static int [] a; static ArrayList<int[]> list = new ArrayList<>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); for (int i = 0; i < n; ++ i) { a = new int [2]; a[0] = in.nextInt(); a[1] = in.nextInt(); list.add(a); } list.sort(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0] - o2[0]; } }); int k = 0; int r = Integer.MIN_VALUE; for (int a[]:list) { // 如果当前区间的左端点大于上一个区间的最右端 // 那么这个区间就是个独立的区间 不需要合并 if (a[0] > r) k ++; r = Math.max(r, a[1]); // 更新右端点 } System.out.println(k); } }
