# Java Solution (26ms, beats 100%)

• First using quick sort applying on the start of each point; then iterative from the beginning of the sorted array by calculating the end of the previous point (intersected points results in e.g. [1,4], [2,5] -> [2,4], end of previous: 4). An virtual point not intersecting the last one was added at the end of the points to fulfill the border condition.

``````public int findMinArrowShots(int[][] points) {
if (points == null || points.length == 0) {
return 0;
}
if (points.length == 1) {
return 1;
}
int length = points.length;
sortStart(points, 0, length - 1);

int i = 0;
int count = 0;
int lastEnd = points[0][1];
int currentStart = 0;
int currentEnd = 0;

while (i < length + 1) {
if (i < length) {
currentStart = points[i][0];
currentEnd = points[i][1];
} else {
currentStart = points[length - 1][1] + 1;
currentStart = points[length - 1][1] + 1;
}
if (lastEnd >= currentStart) {
lastEnd = (lastEnd > currentEnd) ? currentEnd : lastEnd;
} else {
if (i < length) {
lastEnd = points[i][1];
}
count++;
}
i++;
}

return count;
}

private void sortStart(int[][] points, int leftIndex, int rightIndex) {
int i = leftIndex;
int j = rightIndex;
int m = leftIndex + (rightIndex - leftIndex) / 2;
int mValue = points[m][0];

if (i >= j) {
return;
}

while (i < j) {
while (points[i][0] < mValue) {
i++;
}
while (points[j][0] > mValue) {
j--;
}

if (i <= j) {
int tempStart = points[i][0];
points[i][0] = points[j][0];
points[j][0] = tempStart;
int tempEnd = points[i][1];
points[i][1] = points[j][1];
points[j][1] = tempEnd;
i++;
j--;
}
}
sortStart(points, leftIndex, j);
sortStart(points, i, rightIndex);
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.