Mismatched shoe bin
EasyOnline Assessment
Sort a charity bin of loose shoes into pairs.
Every left shoe has a size, and so does every right shoe. The volunteers pair shoes up in two passes:
- Exact pass. A left shoe and a right shoe of the same size make a pair. Pair as many as possible.
- Near pass. Among the shoes still unpaired, a left shoe of size
smay be paired with a right shoe of sizes + 1(the right shoe is one size bigger; the other way round is not allowed). Pair as many as possible.
Shoes that are still unpaired after both passes are leftovers. Because the near pass only sees what the exact pass left behind, the order of the passes matters.
Input: left, a list of integer sizes of the left shoes, and right, a list of integer sizes of the right shoes (in no particular order, possibly empty).
Output: a list [exact, near, left_over, right_over]: the number of pairs from the exact pass, the number from the near pass, the sizes of the unpaired left shoes in ascending order, and the sizes of the unpaired right shoes in ascending order.
Example 1
- Input:
- [[40,41,40],[41,40,41]]
- Output:
- [2,1,[],[]]
- Explanation
- The exact pass pairs 40 with 40 and 41 with 41. The remaining left 40 and right 41 pair in the near pass (right shoe one size bigger):
[2, 1, [], []].
Example 2
- Input:
- [[40,41],[41,42]]
- Output:
- [1,0,[40],[42]]
- Explanation
- The exact pass pairs the 41s. The left 40 would have matched the right 41 in the near pass, but that shoe is already used, and 42 has no left partner. Leftovers: left 40, right 42.
Example 3
- Input:
- [[38,38,39],[37,38]]
- Output:
- [1,0,[38,39],[37]]
- Explanation
- The exact pass pairs one 38 with a 38. The left shoes 38 and 39 would need right shoes 39 and 40; the right 37 is one size smaller than 38, which is not allowed. Both leftover lists are in ascending order.
Constraints
0 <= left.length, right.length <= 2,00020 <= left[i], right[i] <= 60