מציאת המספר החיובי הקטן ביותר במערך טווחים

a הוא מערך המכיל מספרים שלמים ממוין בסדר עולה ממש (כלומר המספרים עולים ולא זהים).

נגדיר מערך טווחים של 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

מערך הטווחים range יהיה:

0	1	2	3
<3, 5>	<12, 12>	<19, 20>	<100, 104>

(כל אינדקס מסומן כזוג סדור עם סוגריים משולשים).

לשם כך הוגדרה מחלקה בשם Range בה כל אובייקט מייצג תחום של מספרים כפי המתואר לעיל. להלן המחלקה Range:

java

בהינתן rangeA (המייצג מערך של מספרים שלמים a ממוינים בסדר עולה ממש). יש להחזיר את הערך של המספר החיובי המינימלי במערך a. אם לא נמצא מספר חיובי במערך, יוחזר -1.

לדוגמה, עבור המערך rangeA הבא:

0	1	2	3
<-7, -3>	<-1, -1>	<4, 6>	<20, 22>

שמייצג את המערך a:

0	1	2	3	4	5	6	7	8	9	10	11
-7	-6	-5	-4	-3	-1	4	5	6	20	21	22

יוחזר הערך 4.

אם נתון שהמערך rangeA יהיה הטווח <-1 ,2>, יוחזר הערך 1.

השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.

אילוצים:

בכל אובייקט מהמחלקה Range הערך small_ תמיד קטן או שווה לערך big_.
אסור להמיר את מערך הטווחים rangeA למערך המספרים השלמים a ולעבוד על המערך a.
אורך הקלט n הוא גודל מערך הטווחים rangeA.

דוגמה 1:

קלט:

rangeA = [[-7, -3], [-1, -1], [4, 6], [20, 22]]

פלט:

הסבר: המספר החיובי הקטן ביותר בטווחים הוא 4.

דוגמה 2:

קלט:

rangeA = [[1, 2]]

פלט:

הסבר: המספר החיובי הקטן ביותר בטווחים הוא 1.

דוגמה 3:

קלט:

rangeA = [[-10, -5], [-3, -1]]

פלט:

-1

הסבר: אין מספרים חיוביים בטווחים.

דוגמה 4:

קלט:

rangeA = [[0, 0], [2, 3], [5, 10]]

פלט:

הסבר: המספר החיובי הקטן ביותר בטווחים הוא 2.

דוגמה 5:

קלט:

rangeA = [[-5, -2], [0, 0], [1, 1]]

פלט:

הסבר: המספר החיובי הקטן ביותר בטווחים הוא 1.

דוגמה 6:

קלט:

rangeA = [[-10, 0], [5, 5], [10, 20]]

פלט:

הסבר: המספר החיובי הקטן ביותר בטווחים הוא 5.

דוגמה 7:

קלט:

rangeA = [[-100, -50], [-25, -10], [0, 0]]

פלט:

-1

הסבר: אין מספרים חיוביים בטווחים.

דוגמה 8:

קלט:

rangeA = [[0, 0], [1, 100]]

פלט:

הסבר: המספר החיובי הקטן ביותר בטווחים הוא 1.

בחר קובץ לעריכה מהתפריט בצד

נשמרLn 1, Col 1

קלט:

rangeA = [[-7, -3], [-1, -1], [4, 6], [20, 22]]

הפלט המבוקש: