a הוא מערך המכיל מספרים שלמים ממוין בסדר עולה ממש (המספרים שונים זה מזה).
נגדיר מערך טווחים (range array) של a כמערך שנבנה באופן הבא: עבור כל רצף של מספרים עוקבים ב-a, יהיה במערך הטווחים אובייקט שמכיל שני שדות של מספרים שלמים. שדה אחד הוא המספר הקטן ביותר ברצף (small) והשני הוא המספר הגדול ביותר ברצף (big). רצף יכול להיות באורך 1 או יותר. אם הרצף באורך 1, הוא מיוצג במערך הטווחים על ידי אובייקט ששני השדות שלו שווים.
לדוגמה, עבור המערך a:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 3 | 4 | 5 | 12 | 19 | 20 | 100 | 101 | 102 | 103 | 104 |
מערך הטווחים rangeA יהיה:
| 0 | 1 | 2 | 3 |
| <3, 5> | <12, 12> | <19, 20> | <100, 104> |
(כל אובייקט מסומן כזוג סדור עם סוגריים משולשים).
לשם כך הוגדרה מחלקה בשם Range בה כל אובייקט מייצג טווח של מספרים לפי המתואר לעיל. להלן המחלקה Range:
כתבו שיטה סטטית יעילה המקבלת כפרמטר מערך טווחים rangeA (המייצג מערך של מספרים שלמים a ממוינים בסדר עולה ממש). השיטה צריכה להחזיר את הערך של המספר השלילי הגדול ביותר במערך a (כלומר, המספר השלילי הקרוב ביותר ל-0). אם אין מספר שלילי ממש במערך a, השיטה תחזיר את הערך Integer.MIN_VALUE (המספר השלם הקטן ביותר האפשרי).
לדוגמה, עבור המערך rangeA הבא:
| 0 | 1 | 2 | 3 |
| <-17, -13> | <-2, -2> | <4, 6> | <20, 22> |
שמייצג את המערך a:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| -17 | -16 | -15 | -14 | -13 | -2 | 4 | 5 | 6 | 20 | 21 | 22 |
השיטה תחזיר את הערך -2.
אם בתא באינדקס 1 של המערך rangeA יהיה הטווח <-2, 1>, השיטה תחזיר את הערך -1.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
Range, הערך _small תמיד קטן או שווה לערך _big.rangeA לא יכול להיות שיהיו שני תאים סמוכים שמייצגים טווח אחד רצוף. לדוגמה, לא ייתכן שיהיו הטווחים <2, 4> ו-<5, 7>. הטווח חייב להיות בתא אחד <2, 7>.a כל המספרים שונים זה מזה.rangeA למערך המספרים השלמים a ולעבוד על המערך a. השיטה אמורה לקבל את מערך הטווחים rangeA בלבד ולעבוד עליו.n הוא גודל מערך הטווחים rangeA. כלומר, בדוגמה לעיל n = 4.rangeA = [<-17, -13>, <-2, -2>, <4, 6>, <20, 22>]
-2
הסבר: המערך a שמיוצג הוא [-17, -16, -15, -14, -13, -2, 4, 5, 6, 20, 21, 22]. המספר השלילי הגדול ביותר הוא -2.
rangeA = [<-5, -2>]
-2
הסבר: המספר השלילי הגדול ביותר בטווחים הוא -2.
rangeA = [<1, 5>, <10, 20>]
-2147483648
הסבר: אין מספרים שליליים בטווחים — מחזירים Integer.MIN_VALUE.
rangeA = [<-10, -5>, <-2, -2>, <0, 0>, <3, 7>]
-2
הסבר: המספר השלילי הגדול ביותר בטווחים הוא -2.
rangeA = [<-3, -1>, <1, 1>, <3, 4>]
-1
הסבר: המספר השלילי הגדול ביותר בטווחים הוא -1.
rangeA = [<-20, -10>, <-5, -5>, <0, 10>]
-5
הסבר: המספר השלילי הגדול ביותר בטווחים הוא -5.
rangeA = [<0, 0>, <10, 50>, <100, 200>]
-2147483648
הסבר: אין מספרים שליליים בטווחים — מחזירים Integer.MIN_VALUE.
rangeA = [<-100, -1>, <1, 1>]
-1
הסבר: המספר השלילי הגדול ביותר בטווחים הוא -1.
rangeA = [<-3, 5>]
-1
הסבר: הטווח חוצה את ה-0 (מתחיל בשלילי ונגמר בחיובי). המספר השלילי הגדול ביותר בטווח הוא -1.
rangeA = [<-50, -10>, <-5, 20>]
-1
הסבר: הטווח האחרון חוצה את ה-0. גם בטווח הקודם יש שליליים (עד -5), אך השלילי הגדול ביותר הוא -1 שנמצא בטווח האחרון.
rangeA = [<-1, 10>]
-1
הסבר: הטווח מתחיל ב--1 וחוצה את ה-0. המספר השלילי הגדול ביותר הוא -1.
rangeA = [<-1000000, 1000000>]
-1
הסבר: טווח גדול מאוד שחוצה את ה-0. המספר השלילי הגדול ביותר הוא -1.
rangeA = [<-1, -1>]
-1
הסבר: טווח של איבר בודד שלילי. המספר השלילי הגדול ביותר הוא -1.
rangeA = [<5, 5>]
-2147483648
הסבר: טווח של איבר בודד חיובי, אין שליליים — מחזירים Integer.MIN_VALUE.
rangeA = [<0, 0>]
-2147483648
הסבר: טווח של איבר בודד שהוא 0, אין שליליים — מחזירים Integer.MIN_VALUE.
rangeA = [<-100, -90>, <-50, -40>, <-10, 10>]
-1
הסבר: מספר טווחים, האחרון חוצה את ה-0. המספר השלילי הגדול ביותר הוא -1 שנמצא בטווח האחרון.
קלט:
rangeA = [<-17, -13>, <-2, -2>, <4, 6>, <20, 22>]
הפלט המבוקש:
-2