Essentially, we treat the input as a set of line segments with different start and end values. If we sort the lines by their start values, and iterate from the smallest start value line, then for a given line segment, what it overlaps can be calculated by counting the lines which start before the end of the give line segment. After we have to remove this line's start value from the start values array, otherwise we get duplicate counts from other line segments overlapping with the one we already counted. When we remove, any duplicate start values won't matter. I tried to implement this using a Line class, creating two arrayLists for start values and lines. Which is somewhat lots of code.
But for this question, there is another input property we can use. Notice that for the input array A, the end value of A[j] line cannot be smaller than the start value of A[i] line if i<j. So we can just sort the start values array and iterate through input array A. For any A[i] and A[j] where i<j, if end value of A[i] is larger than start value of A[j], they must overlap.
Also, be careful with integer overflow.
No comments:
Post a Comment