Sorting an array of zeros, negative and positive numbers with Comparable interface-CodePudding

class pair implements Comparable<pair>{
int x, y;
pair(int x, int y){
    this.x = x;
    this.y = y;
}
public int compareTo(pair c){
    return this.y-c.y;
}}

class Solution {
public int findMinArrowShots(int[][] points) {
    ArrayList<pair> point = new ArrayList<>(); 
    for(int i=0; i<points.length; i  ){
        point.add(new pair(points[i][0], points[i][1]));
    }
    
    Collections.sort(point);
    
    int minarr=1;
    int prev =0;
    for(int i=1; i<point.size(); i  ){
        if(point.get(i).x>point.get(prev).y){
            minarr  ;
            prev = i;
        }
    }
    return minarr;
}}

I want to sort the array on the basis of y coordinate: but with mix of positive and negative y values it is giving me wrong(unsorted) order

for eg: for the I/P : [[-2147483646,-2147483645], [2147483646,2147483647]] I need [-2147483646,-2147483645] first then [2147483646,2147483647] but it is ordering [2147483646,2147483647] as first then [-2147483646,-2147483645].

CodePudding user response：

The problem is that you're running into integer limits. Java integers can't hold more than 2,147,483,647 or less than -2,147,483,648 (see max value of integer), so when you add/subtract them you can end up with integer overflow/underflow, which is what's happening here.

The solution to integer limit issues in general is to use long, which can hold values of up to 9,223,372,036,854,775,808 and as low as -9,223,372,036,854,775,807. However, here that is just stepping around the real issue: that you are inventing your own comparison method from scratch, when a built-in one designed to handle all edge cases already exists.

What you should be doing is calling the built-in compare() on the two y values. Instead of

return this.y - c.y

return Integer.compare(this.y, c.y)

which will call the built-in compare() method for integers, which is built to be able to handle all integers.

CodePudding user response：

   if(point.get(i).x>point.get(prev).y){

Change to:

   if(point.get(i).y>point.get(prev).y){