Skip to content

Instantly share code, notes, and snippets.

@PetrGlad
Created June 24, 2018 10:01
Show Gist options
  • Save PetrGlad/26309a156e94f69bf072588fe7902f6c to your computer and use it in GitHub Desktop.
Save PetrGlad/26309a156e94f69bf072588fe7902f6c to your computer and use it in GitHub Desktop.
Ranges
import java.util.Random;
import java.util.TreeSet;
public class MainSr {
public static void main(String[] args) {
// Run this with assertions enabled
assert 1 == countRanges(new int[]{1});
assert 1 == countRanges(new int[]{2, 1});
assert 1 == countRanges(new int[]{3, 2, 1});
assert 3 == countRanges(new int[]{1, 2, 3});
assert 2 == countRanges(new int[]{2, 1, 3});
assert 3 == countRanges(new int[]{2, 1, 3, 5, 4});
assert 4 == countRanges(new int[]{2, 1, 3, 4, 5});
assert 4 == countRanges(new int[]{1, 3, 2, 4, 5});
largeTimings();
}
private static void largeTimings() {
// Should complete in reasonable time
int a[] = new int[100_000];
Random r = new Random();
for (int c = 0; c < 10; c++) {
for (int i = 0; i < a.length; i++)
a[i] = r.nextInt(1_000_000_000);
System.out.println(countRanges(a));
}
}
public static int countRanges(int[] a) {
final TreeSet<Integer> xs = new TreeSet<>();
for (int x : a)
xs.add(x);
int count = 0;
int idx = 0;
while (idx < a.length && !xs.isEmpty()) {
int x = xs.pollFirst();
while (idx < a.length && x != a[idx]) {
xs.remove(a[idx]);
idx++;
}
count++;
}
assert count > 0;
return count;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment