FastPrep
Problem · Array

Minimum Markers to Clear Line Segments

Learn this problem
● MediumHSBC logoHSBCFULLTIMEOA

Problem statement

You are given two integer arrays startX and endX of equal length. Pair i describes one closed line segment on the X-axis.

Normalize each pair before using it:

  • The segment's left endpoint is min(startX[i], endX[i]).
  • The segment's right endpoint is max(startX[i], endX[i]).

Placing a marker at an X-axis coordinate clears every remaining segment that contains that coordinate, including segments that meet it at an endpoint.

Return the minimum number of marker placements needed to clear all segments. Return 0 when both arrays are empty.

Function

markerPlaced(startX: int[], endX: int[]) → int

Examples

Example 1

startX = [0, 2, 4, -8]endX = [4, 5, 8, -9]return = 2

The normalized segments are [0, 4], [2, 5], [4, 8], and [-9, -8].

A marker at 4 clears the first three segments. A second marker at either -9 or -8 clears the remaining segment. No single coordinate belongs to both the negative segment and the three nonnegative segments, so the minimum is 2.

Constraints

  • 0 <= startX.length = endX.length <= 10^4
  • -10^9 <= startX[i], endX[i] <= 10^9
  • Every endpoint is an integer.

More HSBC problems

drafts saved locally
public int markerPlaced(int[] startX, int[] endX) {
  // Write your code here
}
startX[0, 2, 4, -8]
endX[4, 5, 8, -9]
expected2
checking account