tizianoP
BAN USERpublic static int getMinInsertion(String string) {
char[] inputString = string.toCharArray();
int counter = 0;
int stackSize = 0;
for (int i = 0; i < inputString.length; i++) {
char c = inputString[i];
if (c == ')')
if (stackSize < 1)
counter++;
else
stackSize--;
else
stackSize++;
}
return stackSize + counter;
}
Complexity: O(n log n) in time => due to the initial sort
If the input was already sorted the complexity would be O(n).
public static class Interval {
public Interval(int s, int e) {
this.start = s;
this.end = e;
}
public int start;
public int end;
}
public static List<Interval> clean(List<Interval> ranges) {
Collections.sort(ranges, new Comparator<Interval>() {
@Override
public int compare(Interval int1, Interval int2) {
return int1.start - int2.start;
}
});
List<Interval> output = new ArrayList<>();
int start = ranges.get(0).start;
int end = ranges.get(0).end;
for (int i = 1; i < ranges.size(); i++) {
if (ranges.get(i).start <= end) {
if (ranges.get(i).end > end)
end = ranges.get(i).end;
} else {
Interval interval = new Interval(start, end);
output.add(interval);
start = ranges.get(i).start;
end = ranges.get(i).end;
}
}
Interval interval = new Interval(start, end);
output.add(interval);
return output;
}
It counts how many times the pattern is present (4 directions, brute force)
- tizianoP February 05, 2016